Submission #794433

#TimeUsernameProblemLanguageResultExecution timeMemory
794433firewaterToy Train (IOI17_train)C++14
0 / 100
5 ms2004 KiB
#include "train.h" #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include <cassert> #define ll long long #define MX 20230 using namespace std; int n,m,tot,w,p[MX],a[MX],c[MX],cc[MX],h[MX],H[MX],fr[MX],cy[MX],pp[MX]; vector<int>ls,s[MX]; struct rec { int to,nx; }e[MX],E[MX]; void addl(int x,int y) { e[++tot].to=y; e[tot].nx=h[x]; h[x]=tot; return; } void addll(int x,int y) { E[tot].to=y; E[tot].nx=H[x]; H[x]=tot; return; } void dfs1(int x) { if(c[x])return; p[x]=1; for(int i=h[x];i;i=e[i].nx){ int y=e[i].to; if(p[y])continue; dfs1(y); } ls.push_back(x); return; } void dfs2(int x,int p) { if(c[x])return; fr[x]=p; s[p].push_back(x); for(int i=H[x];i;i=E[i].nx){ int y=E[i].to; if(fr[y])continue; dfs2(y,p); } return; } void dfs3(int x) { pp[x]=1; for(int i=H[x];i;i=E[i].nx){ int y=E[i].to; if(pp[y])continue; dfs3(y); } return; } std::vector<int> who_wins(std::vector<int> A, std::vector<int> C, std::vector<int> U, std::vector<int> V) { std::vector<int> ans(A.size()); n=A.size(); m=U.size(); for(int i=1;i<=n;++i){ a[i]=A[i-1]; c[i]=C[i-1]; } for(int i=0;i<m;++i){ if(U[i]==V[i])cy[U[i]+1]=1; else{ addl(U[i]+1,V[i]+1); addll(V[i]+1,U[i]+1); } } for(int i=1;i<=n;++i) p[i]=0; for(int i=1;i<=n;++i) if(!p[i]) dfs1(i); reverse(ls.begin(),ls.end()); for(int i=0;i<ls.size();++i) if(!fr[ls[i]]) dfs2(ls[i],++w); for(int i=1;i<=n;++i) if(c[i]==0&&(s[fr[i]].size()>1||cy[i]==1)) pp[i]=1; for(int i=1;i<=n;++i) if(p[i]) dfs3(i); for(int i=1;i<=n;++i) ans[i-1]=pp[i]^1; return ans; }

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:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=0;i<ls.size();++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...