Submission #70853

#TimeUsernameProblemLanguageResultExecution timeMemory
70853KmcodeToy Train (IOI17_train)C++14
11 / 100
1495 ms4752 KiB
#include <bits/stdc++.h> using namespace std; //#include "train.h" vector<int> v[5002]; vector<int> rv[5002]; bool use[5002]; int sz[5002]; vector<int> bc; inline void dfs(int b){ use[b]=true; for(int go:v[b]){ if(use[go]==false){ dfs(go); } } bc.push_back(b); } int belong[5002]; inline void dfs2(int b,int be){ use[b]=false; belong[b]=be; sz[be]++; for(int go:rv[b]){ if(use[go]){ dfs2(go,be); } } } int m; int n; void scc(){ for(int i=0;i<n;i++){ if(use[i]==false){ dfs(i); } } reverse(bc.begin(),bc.end()); for(int i=0;i<bc.size();i++){ if(use[bc[i]]){ dfs2(bc[i],m); m++; } } } vector<int> ed[5002]; bool ok[5002]; int us[5002]; int u_s; bool bor[5002]; bool are[5002]; vector<int> r; inline bool a_walk(int node){ us[node]=u_s; if(are[node])return true; if(ok[belong[node]]==false&&sz[belong[node]]>1)return true; for(int go:v[node]){ if(us[go]!=u_s){ if(a_walk(go))return true; } } return false; } inline bool b_walk(int node){ us[node]=u_s; if(bor[node])return true; if(sz[belong[node]]>1)return true; for(int go:v[node]){ if(us[go]!=u_s){ if(b_walk(go))return true; } } return false; } std::vector<int> who_wins(std::vector<int> a1, std::vector<int> r1, std::vector<int> u1, std::vector<int> v1) { r=r1; n=a1.size(); for(int i=0;i<u1.size();i++){ if(u1[i]==v1[i]){ if(r1[u1[i]]){ are[u1[i]]=true; } else{ bor[u1[i]]=true; } continue; } if(r[u1[i]]||r[v1[i]])continue; v[u1[i]].push_back(v1[i]); rv[v1[i]].push_back(u1[i]); } scc(); for(int i=0;i<n;i++){ ok[belong[i]]|=r1[i]; } vector<int> ret(a1.size(),1); for(int i=0;i<n;i++)v[i].clear(); for(int i=0;i<u1.size();i++)v[u1[i]].push_back(v1[i]); for(int i=0;i<n;i++){ u_s++; if(b_walk(i)){ ret[i]=0; } } return ret; }

Compilation message (stderr)

train.cpp: In function 'void scc()':
train.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<bc.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:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u1.size();i++){
              ~^~~~~~~~~~
train.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<u1.size();i++)v[u1[i]].push_back(v1[i]);
                ~^~~~~~~~~~
#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...