Submission #1651110


Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const int INF = (1LL<<30);
#else
const ll INF = (1LL<<60);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], b[100010], dp[2][100010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) cin >> a[i] >> b[i], a[i]--, b[i]--;
  string s;
  cin >> s;

  int idx=0;
  while(!isdigit(s[idx])) ++idx;
  int num = 0;
  while(isdigit(s[idx])) {
    num *= 10;
    num += s[idx]-'0';
    idx++;
  }
  // cout << idx << " " << s[idx] << endl;
  num--;
  // cout << "num:" << num << endl;
  int cur = 0, nxt = 1;
  dp[cur][num] = true;

  // w
  if(s[idx] == 'w') {
    REP(i, m) {
      if(dp[cur][b[i]]) dp[nxt][a[i]] = true;
    }
    idx++;
  } else {
    int cnt = 0;
    REP(i, n) if(dp[cur][i]) cnt++;
    VI c(n);
    REP(i, m) if(dp[cur][b[i]]) c[a[i]]++;
    REP(i, n) if(c[i]!=cnt) dp[nxt][i] = true;
  }
  swap(cur, nxt);
  // cout << "idx:" << idx << endl;
  REP(i, n) {
    dp[nxt][i] = false;
    // cout << dp[cur][i] << " ";
  }
  // cout << endl;

  while(idx < (int)s.size()) {
    ++idx;
    if(s[idx] == 'w') {
      REP(i, m) {
        if(dp[cur][b[i]]) dp[nxt][a[i]] = true;
      }
    } else {
      int cnt = 0;
      REP(i, n) if(dp[cur][i]) cnt++;
      VI c(n);
      REP(i, m) if(dp[cur][b[i]]) c[a[i]]++;
      REP(i, n) if(c[i]!=cnt) dp[nxt][i] = true;
    }

    while(idx < (int)s.size() && s[idx]=='w') ++idx;
    swap(cur, nxt);
    // cout << "idx:" << idx << endl;
    REP(i, n) {
      dp[nxt][i] = false;
      // cout << dp[cur][i] << " ";
    }
    // cout << endl;
  }

  int ret = 0;
  REP(i, n) if(dp[cur][i]) ret++;
  cout << ret << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 敵対的引用
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2416 Byte
Status AC
Exec Time 14 ms
Memory 1416 KB

Judge Result

Set Name small large
Score / Max Score 50 / 50 50 / 50
Status
AC × 33
AC × 63
Set Name Test Cases
small small/00_sample1, small/00_sample2, small/00_sample3, small/10_random08, small/10_random103, small/10_random119, small/10_random126, small/10_random127, small/10_random131, small/10_random146, small/10_random158, small/10_random159, small/10_random18, small/10_random192, small/10_random205, small/10_random269, small/10_random27, small/10_random276, small/10_random29, small/10_random312, small/10_random332, small/10_random339, small/10_random384, small/10_random43, small/10_random453, small/10_random457, small/10_random466, small/10_random474, small/10_random492, small/10_random53, small/10_random532, small/10_random550, small/10_random86
large small/00_sample1, small/00_sample2, small/00_sample3, small/10_random08, small/10_random103, small/10_random119, small/10_random126, small/10_random127, small/10_random131, small/10_random146, small/10_random158, small/10_random159, small/10_random18, small/10_random192, small/10_random205, small/10_random269, small/10_random27, small/10_random276, small/10_random29, small/10_random312, small/10_random332, small/10_random339, small/10_random384, small/10_random43, small/10_random453, small/10_random457, small/10_random466, small/10_random474, small/10_random492, small/10_random53, small/10_random532, small/10_random550, small/10_random86, large/20_large601, large/20_large602, large/20_large603, large/20_large605, large/20_large606, large/20_large608, large/20_large611, large/20_large616, large/20_large620, large/20_large634, large/20_large643, large/20_large646, large/20_large647, large/20_large651, large/20_large667, large/20_large677, large/20_large680, large/20_large692, large/20_large700, large/20_large711, large/20_large721, large/20_large723, large/20_large725, large/20_large726, large/20_large734, large/20_large736, large/20_large740, large/20_large751, large/20_large752, large/20_large765
Case Name Status Exec Time Memory
large/20_large601 AC 5 ms 384 KB
large/20_large602 AC 6 ms 384 KB
large/20_large603 AC 4 ms 384 KB
large/20_large605 AC 4 ms 384 KB
large/20_large606 AC 12 ms 512 KB
large/20_large608 AC 12 ms 636 KB
large/20_large611 AC 14 ms 1044 KB
large/20_large616 AC 3 ms 256 KB
large/20_large620 AC 7 ms 512 KB
large/20_large634 AC 4 ms 384 KB
large/20_large643 AC 12 ms 1212 KB
large/20_large646 AC 6 ms 384 KB
large/20_large647 AC 6 ms 384 KB
large/20_large651 AC 7 ms 512 KB
large/20_large667 AC 5 ms 640 KB
large/20_large677 AC 5 ms 384 KB
large/20_large680 AC 10 ms 512 KB
large/20_large692 AC 4 ms 384 KB
large/20_large700 AC 8 ms 952 KB
large/20_large711 AC 6 ms 512 KB
large/20_large721 AC 5 ms 384 KB
large/20_large723 AC 3 ms 384 KB
large/20_large725 AC 6 ms 512 KB
large/20_large726 AC 5 ms 384 KB
large/20_large734 AC 10 ms 1416 KB
large/20_large736 AC 3 ms 256 KB
large/20_large740 AC 4 ms 512 KB
large/20_large751 AC 4 ms 384 KB
large/20_large752 AC 4 ms 384 KB
large/20_large765 AC 5 ms 384 KB
small/00_sample1 AC 1 ms 256 KB
small/00_sample2 AC 1 ms 256 KB
small/00_sample3 AC 1 ms 256 KB
small/10_random08 AC 1 ms 256 KB
small/10_random103 AC 2 ms 256 KB
small/10_random119 AC 4 ms 256 KB
small/10_random126 AC 2 ms 256 KB
small/10_random127 AC 1 ms 256 KB
small/10_random131 AC 2 ms 256 KB
small/10_random146 AC 3 ms 256 KB
small/10_random158 AC 1 ms 256 KB
small/10_random159 AC 2 ms 256 KB
small/10_random18 AC 1 ms 256 KB
small/10_random192 AC 2 ms 256 KB
small/10_random205 AC 2 ms 256 KB
small/10_random269 AC 5 ms 384 KB
small/10_random27 AC 2 ms 256 KB
small/10_random276 AC 1 ms 256 KB
small/10_random29 AC 6 ms 384 KB
small/10_random312 AC 2 ms 256 KB
small/10_random332 AC 1 ms 256 KB
small/10_random339 AC 2 ms 256 KB
small/10_random384 AC 4 ms 256 KB
small/10_random43 AC 2 ms 256 KB
small/10_random453 AC 1 ms 256 KB
small/10_random457 AC 1 ms 256 KB
small/10_random466 AC 1 ms 256 KB
small/10_random474 AC 4 ms 256 KB
small/10_random492 AC 2 ms 256 KB
small/10_random53 AC 3 ms 256 KB
small/10_random532 AC 2 ms 256 KB
small/10_random550 AC 1 ms 256 KB
small/10_random86 AC 3 ms 256 KB