Submission #800496

#TimeUsernameProblemLanguageResultExecution timeMemory
800496FEDIKUSStations (IOI20_stations)C++17
76 / 100
747 ms792 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; const int maxn=1010; int t=0; int tin[maxn]; int tout[maxn]; int res[maxn]; vector<int> g[maxn]; void dfs(int node,int d=0,int par=-1){ tin[node]=t++; for(int i:g[node]){ if(i==par) continue; dfs(i,d+1,node); } tout[node]=t++; if(d&1) res[node]=tin[node]; else res[node]=tout[node]; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { vector<int> labels(n); for(int i=0;i<n;i++) g[i].clear(); for(int i=0;i<n-1;i++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } t=0; dfs(0); for(int i=0;i<n;i++) labels[i]=res[i]; return labels; } int find_next_station(int s, int t, vector<int> c) { int maxi=*max_element(c.begin(),c.end()); vector<pair<int,int> > decoo(int(c.size())-1); if(maxi>s){ // on je in int cale=c.back(); c.pop_back(); for(int i=0;i<int(c.size());i++) decoo[i].second=c[i]; int prosli=s; for(int i=0;i<int(c.size());i++){ decoo[i].first=prosli+1; prosli=decoo[i].second; } for(int i=0;i<int(c.size());i++){ if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].second; } return cale; }else{ //on je out int cale=c.front(); c.erase(c.begin()); for(int i=0;i<int(c.size());i++) decoo[i].first=c[i]; int prosli=s; for(int i=int(c.size())-1;i>=0;i--){ decoo[i].second=prosli-1; prosli=decoo[i].first; } for(int i=0;i<int(c.size());i++){ if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].first; } return cale; } 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...