Submission #761357

#TimeUsernameProblemLanguageResultExecution timeMemory
761357minhcoolToy Train (IOI17_train)C++17
26 / 100
203 ms15576 KiB
#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(r[v]) continue; if(out[v]) continue; deg[v]++; if(a[v] == 1 && deg[v] == 1) q.push(v); if(a[v] == 0 && deg[v] == deg2[v]) q.push(v); } //vis[u] = 1; //for(auto v : Adj[u]){ // if(vis[v] || out[v]) continue; // q.push(v); //} } //cout << "\n"; for(int i = 0; i < n; i++){ if(!out[i] && !vis[i]) q.push(i); vis[i] = deg[i] = 0; } while(!q.empty()){ int u = q.front(); //cout << "OK " << 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] == 0 && deg[v] == 1) q.push(v); if(a[v] == 1 && deg[v] == deg2[v]) q.push(v); } } //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++; } 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"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); process(); } #endif

Compilation message (stderr)

train.cpp:21:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | 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:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0; i < U.size(); i++){
      |                 ~~^~~~~~~~~~
train.cpp:79:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   79 |    vis[i] = deg[i] = 0;
      |             ~~~~~~~^~~
#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...