Submission #65156

#TimeUsernameProblemLanguageResultExecution timeMemory
65156mohammad_kilaniToy Train (IOI17_train)C++17
12 / 100
100 ms3188 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; const int N = 5010; vector< int > res , a , r , g[N] , g2[N]; int n , out[N] , out2[N] , last , vis[N] , vi; bool have[N]; void make(int node){ for(int i=0;i<g2[node].size();i++){ if(a[node] == 1 && node == g2[node][i] && r[node] == 0) continue; if(res[g2[node][i]] != -1) continue; out[g2[node][i]]--; if(a[node] == a[g2[node][i]]){ if(res[node] == a[node]){ res[g2[node][i]] = a[node]; make(g2[node][i]); } else{ if(out[g2[node][i]] == 0){ res[g2[node][i]] = a[node] ^ 1; make(g2[node][i]); } } } else{ if(res[node] != a[node]){ res[g2[node][i]] = a[node] ^ 1; make(g2[node][i]); } else{ if(out[g2[node][i]] == 0){ res[g2[node][i]] = a[node]; make(g2[node][i]); } } } } } void make2(int node){ for(int i=0;i<g2[node].size();i++){ if(have[g2[node][i]] || res[g2[node][i]] != -1) continue; out2[g2[node][i]]--; if(out2[g2[node][i]] == 0){ have[g2[node][i]] = true; make2(g2[node][i]); continue; } if(a[g2[node][i]] == 1){ have[g2[node][i]] = true; make2(g2[node][i]); } } } bool DFS(int node){ if(a[node] == 0) return (res[node] == 1); if(node == last) return true; vis[node] = vi; for(int i=0;i<g[node].size();i++){ if(vis[g[node][i]] != vi && DFS(g[node][i])) return true; } return false; } std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) { a = A; n = (int)a.size(); r = R; res.resize(n , -1); for(int i = 0;i<(int)u.size();i++){ g[u[i]].push_back(v[i]); g2[v[i]].push_back(u[i]); out[u[i]]++; out2[u[i]]++; } for(int i=0;i<n;i++){ if(have[i]) continue; have[i] = r[i]; if(have[i] || out2[i] == 0) make2(i); } for(int i = 0;i<(int)u.size();i++){ if(u[i] == v[i] && a[i] == 1 && r[i] == 0) out[u[i]]--; if(u[i] == v[i] && a[i] == 0 && r[i] == 1) out[u[i]]--; if(out[u[i]] == 0){ res[i] = a[i] ^ 1; make(i); } } for(int i=0;i<n;i++){ if(res[i] != -1) continue; if(!have[i]){ res[i] = 0; make(i); } } for(int i=0;i<n;i++){ if(res[i] == -1 && a[i] == 0){ res[i] = 1; make(i); } } for(int i=0;i<n;i++){ if(res[i] != -1) continue; last = i; vi++; if(r[i]){ for(int j = 0;j<g[i].size();j++){ if(vis[g[i][j]] != vi && DFS(g[i][j])){ res[i] = 1; break; } } if(res[i] != -1) make(i); } } for(int i=0;i<n;i++){ if(res[i] == -1) res[i] = 0; } return res; }

Compilation message (stderr)

train.cpp: In function 'void make(int)':
train.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'void make2(int)':
train.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS(int)':
train.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:117:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0;j<g[i].size();j++){
                  ~^~~~~~~~~~~~
#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...