# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955090 | 2024-03-29T11:07:21 Z | Trisanu_Das | Stations (IOI20_stations) | C++17 | 0 ms | 0 KB |
#include "stations.h" #include<bits/stdc++.h> using namespace std; #include <vector> #define pb push_back #define fi first #define se second #define pb push_back typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 5e5 + 5, oo = 1e18 + 7; int n; vector<int> Adj[N]; int l[N], r[N], d[N]; vector<int> vis; void dfs(int u, int p){ vis.pb(u); l[u] = vis.size(); for(auto v : Adj[u]){ if(v == p) continue; d[v] = d[u] + 1; dfs(v, u); vis.pb(u); } r[u] = vis.size(); } int tol[1005][1005]; ii tol2[600005]; vector<int> label(int n_, int k, vector<int> u, vector<int> v) { n = n_; vis.clear(); for(int i = 0; i < n; i++) Adj[i].clear(); for(int i = 0; i < (n - 1); i++){ Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]); } dfs(0, 0); vector<int> labels(n); for(int i = 0; i < n; i++){ if(!(d[i] & 1)) labels[i] = l[i]; else labels[i] = r[i]; } return labels; int find_next_station(int s, int t, vector<int> c) { int mini = oo; for(auto it : c) mini = min(mini, it); if(mini < s){ for(int i = 1; i < c.size(); i++){ int le = c[i], ri; if(i != c.size() - 1) ri = c[i + 1] - 1; else ri = s; if(le <= t && ri >= t) return c[i]; } return c[0]; } else{ for(int i = 0; (i + 1) < c.size(); i++){ int le = (i ? c[i - 1] + 1 : s + 1), ri = c[i]; if(le <= t && ri >= t) return c[i]; } return c.back(); } }