Submission #563773

#TimeUsernameProblemLanguageResultExecution timeMemory
563773Leo121Stations (IOI20_stations)C++14
100 / 100
839 ms772 KiB
#include "stations.h" #include <bits/stdc++.h> #include <vector> #define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i) #define for0(i, n) for(int i = 0; i < int(n); ++ i) #define for1(i, n) for(int i = 1; i <= int(n); ++ i) #define pb push_back using namespace std; typedef vector<int> vi; const int maxn = 1e3; vi tree[maxn]; vi num; int mayor[maxn]; int aux; void dfs(int u, int p){ num[u] = ++ aux; mayor[u] = aux; for(auto v : tree[u]){ if(v == p){ continue; } dfs(v, u); mayor[u] = mayor[v]; } } void asignar(int u, int p, int niv){ if(u){ if(niv % 2){ num[u] = mayor[u]; } num[u] -= niv / 2; } for(auto v : tree[u]){ if(v == p){ continue; } asignar(v, u, niv + 1); } } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { num.clear(); num.resize(n); for0(i, maxn){ tree[i].clear(); } for0(i, n - 1){ tree[u[i]].pb(v[i]); tree[v[i]].pb(u[i]); } aux = -1; dfs(0, 0); asignar(0, 0, 0); return num; } int find_next_station(int s, int t, std::vector<int> c) { if((int) c.size() == 1){ return c[0]; } int li = 1, ls = c.size() - 1, mitad; if(!s){ while(li <= ls){ mitad = (li + ls) / 2; if(t > c[mitad - 1] && t <= c[mitad]){ return c[mitad]; } if(t > c[mitad]){ li = mitad + 1; } else{ ls = mitad - 1; } } return c[0]; } if(s > c[0]){ ls --; while(li <= ls){ mitad = (li + ls) / 2; if(t >= c[mitad] && t < c[mitad + 1]){ return c[mitad]; } if(t > c[mitad]){ li = mitad + 1; } else{ ls = mitad - 1; } } return (t >= c[(int) c.size() - 1] && t < s) ? c[(int) c.size() - 1] : c[0]; } ls --; while(li <= ls){ mitad = (li + ls) / 2; if(t <= c[mitad] && t > c[mitad - 1]){ return c[mitad]; } if(t > c[mitad]){ li = mitad + 1; } else{ ls = mitad - 1; } } return (t <= c[0] && t > s) ? c[0] : c[(int) c.size() - 1]; }
#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...