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 |
|
|
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 |