# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
546760 | brunnorezendes | Stations (IOI20_stations) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "stations.h"
#include <bits/stdc++.h>
#define maxn 1001
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;
int cont;
vi dfs(int n, int x, vvi g, int pai, vi resp, int k){
int i;
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pai){
resp = dfs(n, g[x][i], g, x, resp);
}
}
resp[x] = cont++;
resp[x] = min(resp[x], k);
return resp;
}
vi label(int n, int k, vi u, vi v){
vvi g = vvi(n);
vi resp = vi(n, 0);
for(int i=0;i<n-1;i++){
g[u[i]].push_back(v[i]);
}
cont = 1;
return dfs(n, 0, g, 0, resp, k);
}
int find_next_station(int s, int t, vi c){
int l=0, r=c.size()-1, mid;
while(r>l){
mid = (l+r)/2;
if(t<=c[mid]){
r = mid;
}
else l = mid+1;
}
return c[l];
}