Submission #1195938

#TimeUsernameProblemLanguageResultExecution timeMemory
1195938simona1230Stations (IOI20_stations)C++20
100 / 100
310 ms5288 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; vector<int> g[200001]; int in[200001],out[200001]; int d[200001]; vector<int> l; pair<int,int> h[200001]; int num; void dfs(int i,int p) { in[i]=num++; for(int j=0;j<g[i].size();j++) { int nb=g[i][j]; if(nb==p)continue; d[nb]=d[i]+1; dfs(nb,i); } out[i]=num++; if(d[i]%2==0)l[i]=in[i]; else l[i]=out[i]; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { num=0; l.clear(); for(int i=0;i<n;i++) l.push_back(0); 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]); dfs(0,-1); for(int i=0;i<n;i++) h[i].first=l[i],h[i].second=i; sort(h,h+n); for(int i=0;i<n;i++) l[h[i].second]=i; return l; } int find_next_station(int s, int t, std::vector<int> c) { if(s==0) { for(int i=0;i<c.size();i++) { if(t<=c[i])return c[i]; } } if(s<c[0]) { for(int i=0;i<c.size()-1;i++) { int lf=s; if(i!=0)lf=c[i-1]; if(lf<t&&t<=c[i])return c[i]; } return c[c.size()-1]; } for(int i=c.size()-1;i>0;i--) { int rt=s; if(i!=c.size()-1)rt=c[i+1]; if(c[i]<=t&&t<rt)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...