Submission #312423

#TimeUsernameProblemLanguageResultExecution timeMemory
312423QAQAutoMatonStations (IOI20_stations)C++17
100 / 100
1005 ms1124 KiB
#include "stations.h" #include <vector> std::vector<int> to[1005]; std::vector<int> dfn; int t; void dfs(int x,int f,int dp){ if(!dp)dfn[x]=++t; for(auto i:to[x])if(i!=f)dfs(i,x,dp^1); if(dp)dfn[x]=++t; } std::vector<int> label(int n, int, std::vector<int> u, std::vector<int> v) { t=-1; for (int i = 0; i < n; i++) { to[i].clear(); } dfn.resize(n); for(int i=0;i<n-1;++i)to[u[i]].emplace_back(v[i]),to[v[i]].emplace_back(u[i]); dfs(0,-1,0); return dfn; } int find_next_station(int s, int t, std::vector<int> c) { if(c.size()==1)return c[0]; int m=c.size()-1; if(s==0){ for(auto i:c)if(t<=i)return i; } if(c[0]>s){ if(t>s)for(int i=0;i<m;++i)if(t<=c[i])return c[i]; return c[m]; } else{ if(t<s)for(int i=m;i;--i)if(t>=c[i])return c[i]; return c[0]; } }
#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...