Submission #64839

#TimeUsernameProblemLanguageResultExecution timeMemory
64839mohammad_kilaniToy Train (IOI17_train)C++17
11 / 100
407 ms1964 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; const int N = 5010; vector< int > res , a , g[N] , r , g2[N]; int n , vis[N] , vi = 0 , last , out[N]; bool have[N]; void make(int node){ for(int i=0;i<g2[node].size();i++){ if(res[g2[node][i]] != -1) continue; out[g2[node][i]]--; if(a[g2[node][i]] == a[node]){ 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]){ if(out[g2[node][i]] == 0){ res[g2[node][i]] = a[node]; make(g2[node][i]); } } else{ res[g2[node][i]] = a[node] ^ 1; make(g2[node][i]); } } } } bool DFS(int node){ vis[node] = vi; if(a[node] == 0 && r[node]) return false; if(node == last) return true; for(int i=0;i<g[node].size();i++){ if(vis[g[node][i]] != vi && a[g[node][i]] == a[last]){ if(DFS(g[node][i])) return true; } } return false; } bool DFS3(int node){ vis[node] = vi; if(have[node]) return true; if(a[node] != a[last]) return false; for(int i=0;i<g[node].size();i++){ if(vis[g[node][i]] != vi && DFS3(g[node][i])) return true; } return false; } bool DFS2(int node){ if(res[node] != -1 || have[node]) return false; if(node == last) return true; vis[node] = vi; for(int i=0;i<g[node].size();i++){ if(vis[g[node][i]] != vi && DFS2(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<n;i++) have[i] = r[i]; for(int i = 0;i<(int)u.size();i++){ g[u[i]].push_back(v[i]); g2[v[i]].push_back(u[i]); } for(int i=0;i<n;i++){ if(res[i] != -1) continue; last = i; vi++; if(a[i] == 0 || r[i]){ for(int j = 0;j<g[i].size();j++){ if(a[g[i][j]] == a[i] && vis[g[i][j]] != vi && DFS(g[i][j])){ res[i] = a[i]; break; } } } if(res[i] != -1) make(i); } for(int i=0;i<n;i++){ if(a[i] == 1){ vi++; have[i] = DFS3(i); } } for(int i=0;i<n;i++){ if(res[i] == -1 && a[i] == 0){ vi++; last = i; if(DFS2(i)){ res[i] = 0; make(i); } } } for(int i=0;i<n;i++){ if(res[i] == -1 && a[i] == 0){ res[i] = a[i] ^ 1; make(i); } } for(int i=0;i<n;i++) if(res[i] == -1) res[i] = a[i] ^ 1; return res; }

Compilation message (stderr)

train.cpp: In function 'void make(int)':
train.cpp:11: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:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS3(int)':
train.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS2(int)':
train.cpp:75: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:99: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...