Submission #1175961

#TimeUsernameProblemLanguageResultExecution timeMemory
1175961adkjtStations (IOI20_stations)C++20
0 / 100
1 ms504 KiB
#include "stations.h" #include <vector> #include<bits/stdc++.h> using namespace std; vector<int> g[1111]; int lab[1111],sz[1111];//,mn=0,mx=1000; void dfs(int now,int p) { for(auto x:g[now]) { if(x==p) continue; //cout<<now<<' '<<x<<'\n'; dfs(x,now); sz[now]+=sz[x]; } } void dfs2(int now,int p,int mn,int mx,int t) { int sumsz=0; for(auto x:g[now]) { if(x==p) continue; if(t) dfs2(x,now,sumsz+mn,sumsz+mn+sz[x]-1,t==0); else dfs2(x,now,mn+1+sumsz,mn+sumsz+sz[x],t==0); sumsz+=sz[x]; } if(t) lab[now]=mx; else lab[now]=mn; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { std::vector<int> labels(n); for(int i=0;i<n-1;i++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } for(int i=0;i<n;i++) sz[i]=1; dfs(0,-1); dfs2(0,-1,0,k,0); for(int i=0;i<n;i++) labels[i]=lab[i],cout<<lab[i]<<' '; return labels; } int find_next_station(int s, int t, std::vector<int> c) { if(s<c[0]) { if(t<s||t>=c[c.size()-1]) return c[c.size()-1]; for(int i=0;i<c.size()-1;i++) { if(t<=c[i]) return c[i]; } return c[c.size()-1]; } else { if(t>s||t<=c[0]) return c[0]; for(int i=1;i<c.size();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...