Submission #429099

#TimeUsernameProblemLanguageResultExecution timeMemory
429099REALITYNBToy Train (IOI17_train)C++14
22 / 100
2093 ms197488 KiB
#include <bits/stdc++.h> #include "train.h" using namespace std; const int N = 5001 ; vector<int> adj[N] ; void dfs(int i , vector<int>&vis,bool flg , vector<int>& r ){ vis[i]=1 ; for(int x: adj[i]){ if(flg){ if(vis[x]==0&&r[x]==0){ dfs(x,vis,flg,r); } continue ; } if(vis[x]==0) dfs(x,vis,flg,r) ; } return ; } vector<int> who_wins0(vector<int> a,vector<int> r,vector<int> u,vector<int>v){ int n = a.size() ; for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]) ; vector<vector<int>> reachable(n) ; for(int i=0;i<n;i++){ reachable[i].resize(n) ; dfs(i,reachable[i],0,r); reachable[i][i]=0 ; for(int x : adj[i]) if(x==i) reachable[i][i]=1; } vector<int> cycle(n) ; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(reachable[i][j]&&reachable[j][i]){ cycle[i]=1; } } } //////////// vector<vector<int>> reachablee(n) ; for(int i=0;i<n;i++){ reachablee[i].resize(n); if(r[i]) continue ; dfs(i,reachablee[i],1,r) ; reachablee[i][i]=0; for(int x: adj[i]) if(x==i) reachablee[i][i]=1 ; } //////////// vector<int> cyclee(n) ; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(reachablee[i][j]&&reachablee[j][i]){ cyclee[j]=1; } } } //////////// vector<int> ans(n,1) ; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(adj[j].empty()&&(reachable[i][j]||i==j)){ ans[i]=0; break; } if(cyclee[j]&&(reachable[i][j]||i==j)){ ans[i]=0 ; break ; } } } return ans ; } vector<int> who_wins1(vector<int> a,vector<int> r,vector<int> u,vector<int>v){ int n = a.size() ; for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]) ; vector<vector<int>> reachable(n) ; for(int i=0;i<n;i++){ reachable[i].resize(n) ; dfs(i,reachable[i],0,r); reachable[i][i]=0 ; for(int x : adj[i]) if(x==i) reachable[i][i]=1; } vector<int> cycle(n) ; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(reachable[i][j]&&reachable[j][i]){ cycle[i]=1; } } } vector<int> ans(n) ; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(cycle[j]&&(reachable[i][j]||i==j)&&r[j]){ ans[i]=1 ; break ; } } } return ans ; } vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int>v){ if(a[0]==0) return who_wins0(a,r,u,v); return who_wins1(a,r,u,v); }

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins0(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]) ;
      |                 ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins1(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[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...