Submission #761351

#TimeUsernameProblemLanguageResultExecution timeMemory
761351minhcoolToy Train (IOI17_train)C++17
0 / 100
8 ms8020 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]; bool out[N]; int deg[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]); //Adj[U[i]].pb(V[i]); } 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] == Adj[v].size()) 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]) continue; if(!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(r[v]) continue; if(out[v]) continue; deg[v]++; if(a[v] == 0 && deg[v] == 1) q.push(v); if(a[v] == 1 && deg[v] == Adj[v].size()) q.push(v); } } //exit(0); int cnt = 0; for(int i = 0; i < n; i++){ if(out[i] || !vis[i]) continue; out[i] = 1; 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: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++){
      |                 ~~^~~~~~~~~~
train.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if(a[v] == 0 && deg[v] == Adj[v].size()) q.push(v);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~
train.cpp:79:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   79 |    vis[i] = deg[i] = 0;
      |             ~~~~~~~^~~
train.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if(a[v] == 1 && deg[v] == Adj[v].size()) q.push(v);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~
#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...