Submission #1061342

#TimeUsernameProblemLanguageResultExecution timeMemory
1061342vjudge1Toy Train (IOI17_train)C++17
5 / 100
39 ms26152 KiB
// #include "train.h" #include<bits/stdc++.h> using namespace std; const int N = 5000 + 10; vector<int> G[N], I[N]; bool good[N], dead[N]; bool R[N], seen[N][N]; int n; bool dfs(int v, int s) { seen[v][s] = true; if(good[v]) return 1; bool ok = 0; for(int u : G[v]) { if(seen[u][s]) continue; ok |= dfs(u, s); } return ok; } vector<int> st; bool S[N]; int scc[N]; void dfs_scc(int v) { S[v] = true; for(int u : G[v]) if(!S[u] && !dead[u]) dfs_scc(u); st.push_back(v); } void dfs_inv_scc(int v, int sc) { S[v] = true; scc[v] = sc; for(int u : I[v]) if(!S[u] && !dead[u]) dfs_inv_scc(u, sc); } void find_good() { for(int i = 0; i < n; i ++) { scc[i] = -1; for(int u : G[i]) I[i].push_back(u); if(dead[i]) continue; dfs_scc(i); } for(int i = 0; i < n; i ++) S[i] = false; while(st.size()) { int u = st.back(); st.pop_back(); if(S[u]) continue; dfs_inv_scc(u, u); } } vector<int> Arezou() { vector<int> w(n); find_good(); // a vertex is good if in its scc we have one charged vertex and at least have 1 edge int e[n] = {}, ch[n] = {}; for(int i = 0; i < n; i ++) { ch[scc[i]] += R[i]; for(int u : G[i]) if(scc[i] == scc[u]) e[scc[i]]++; } for(int i = 0; i < n; i++) good[i] = (ch[scc[i]] > 0 && e[scc[i]] > 0); for(int s = 0; s < n; s++) w[s] = dfs(s, s); return w; } vector<int> Borzou() { for(int i = 0; i < n; i ++) dead[i] = R[i]; vector<int> w(n); find_good(); int e[n] = {}; for(int i = 0; i < n; i ++) { if(dead[i]) continue; for(int u : G[i]) if(scc[i] == scc[u]) e[scc[i]]++; } for(int i = 0; i < n; i ++) if(!dead[i]) good[i] = (e[scc[i]] > 0); for(int s = 0; s < n; s++) w[s] = dfs(s, s); return w; } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { n = a.size(); for(int i = 0; i < n; i ++) { G[i].clear(), I[i].clear(); R[i] = S[i] = good[i] = dead[i] = false; for(int j = 0; j < n; j ++) seen[i][j] = false; } for(int i = 0; i < u.size(); i ++) G[u[i]].push_back(v[i]); for(int i = 0; i < n; i ++) R[i] = r[i]; vector<int> w(n); int c = count(a.begin(), a.end(), 1); if(c == a.size()) return Arezou(); // if(c == 0) //return Borzou(); for(int i = 0; i < n; i++) { int s = i; while(true) { // do I have a cycle bool cycle = false; for(int c : G[s]) if(c == s) cycle = true; if(cycle) { if(G[s].size() == 1) { w[i] = r[s]; break; } if(r[s]) { if(a[s] == 1) { w[i] = 1; break; } s++; continue; } if(a[s] == 1) { s++; continue; } else { w[i] = 0; break; } } else { if(G[s].size()) s++; else { w[i] = 0; break; } } } } return w; }

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for(int i = 0; i < u.size(); i ++)
      |                  ~~^~~~~~~~~~
train.cpp:142:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   if(c == a.size())
      |      ~~^~~~~~~~~~~
#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...