Submission #761379

#TimeUsernameProblemLanguageResultExecution timeMemory
761379minhcoolToy Train (IOI17_train)C++17
100 / 100
395 ms15564 KiB
//#define local #ifndef local #include "train.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; int n, a[N]; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } vector<int> Adj[N], Adj2[N]; bool out[N]; int deg[N], deg2[N]; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> U, vector<int> V){ n = a.size(); for(int i = 0; i < U.size(); i++){ Adj[V[i]].pb(U[i]); Adj2[U[i]].pb(V[i]); //Adj[U[i]].pb(V[i]); } for(int i = 0; i < n; i++) deg2[i] = Adj2[i].size(); while(1){ vector<bool> vis(n + 1); for(int i = 0; i < n; i++){ if(out[i]) continue; vis[i] = r[i]; deg[i] = 0; } queue<int> q; for(int i = 0; i < n; i++){ if(out[i]) continue; if(r[i]) q.push(i); } while(!q.empty()){ int u = q.front(); // cout << u << "\n"; vis[u] = 1; q.pop(); for(auto v : Adj[u]){ if(vis[v]) continue; if(out[v]) continue; deg[v]++; if(a[v] == 1 && deg[v] == 1){ q.push(v); vis[v] = 1; } if(a[v] == 0 && deg[v] == deg2[v]){ q.push(v); vis[v] = 1; } } //vis[u] = 1; //for(auto v : Adj[u]){ // if(vis[v] || out[v]) continue; // q.push(v); //} } while(!q.empty()) q.pop(); //cout << "\n"; for(int i = 0; i < n; i++){ if(!out[i] && !vis[i]){ // if(i == 3015) cout << "????\n"; q.push(i); vis[i] = 1; // cout << "OK " << i << "\n"; } else vis[i] = 0; deg[i] = 0; } while(!q.empty()){ int u = q.front(); q.pop(); //cout << "OK " << u << "\n"; vis[u] = 1; //if(u == 3015) cout << u << "\n"; for(auto v : Adj[u]){ if(vis[v]) continue; if(out[v]) continue; deg[v]++; // if(v == 853) cout << u << " " << a[v] << " " << deg[v] << " " << deg2[v] << " "<< vis[v] << "\n"; if(a[v] == 0 && deg[v] == 1){ // if(v == 3015) cout << "???\n"; q.push(v); vis[v] = 1; } if(a[v] == 1 && deg[v] == deg2[v]){ // if(v == 3015) cout << "???\n"; q.push(v); vis[v] = 1; } } } //exit(0); int cnt = 0; for(int i = 0; i < n; i++){ if(out[i] || !vis[i]) continue; // cout << i << "\n"; out[i] = 1; for(auto it : Adj[i]) deg2[it]--; cnt++; } // cout << out[853] << "\n"; if(!cnt) break; } vector<int> ans; for(int i = 0; i < n; i++) ans.pb(!out[i]); return ans; } //#define local #ifdef local void process(){ int n, m; cin >> n >> m; vector<int> v1, v2; v1.resize(n), v2.resize(n); vector<int> v3, v4; for(int i = 0; i < n; i++) cin >> v1[i]; for(int i = 0; i < n; i++) cin >> v2[i]; for(int i = 0; i < m; i++){ int x, y; cin >> x >> y; v3.pb(x), v4.pb(y); } vector<int> v = who_wins(v1, v2, v3, v4); for(int i = 0; i < n; i++) cout << v[i] << " "; cout << "\n"; //for(int i = 0; i < n; i++) if(v[i]) cout << i << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("train.inp", "r", stdin); process(); } #endif

Compilation message (stderr)

train.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < U.size(); i++){
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...