Submission #1205753

#TimeUsernameProblemLanguageResultExecution timeMemory
1205753notmeStations (IOI20_stations)C++20
76 / 100
310 ms620 KiB
#include "stations.h" #include <bits/stdc++.h> #define pb push_back using namespace std; const int maxn = 2e3 + 10; vector < int > g[maxn]; int tmr = -1; int used[maxn]; int tin[maxn], tout[maxn], depth[maxn]; void dfs(int beg, int from, int h) { used[beg] = 1; depth[beg] = h; tmr ++; tin[beg] = tmr; for (auto nb: g[beg]) { if(used[nb])continue; dfs(nb, beg, h+1); } tmr ++; tout[beg] = tmr; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { memset(used, 0, sizeof(used)); for (int i = 0; i < n; ++ i) g[i].clear(); for (int i = 0; i < n; ++ i) tin[i] = tout[i] = 0; tmr = -1; for (int i = 0; i < n-1; ++ i) { g[u[i]].pb(v[i]); g[v[i]].pb(u[i]); } dfs(0, -1, 0); std::vector<int> labels(n); for (int i = 0; i < n; i++) { if(depth[i] & 1)labels[i] = tout[i]; else labels[i] = tin[i]; } return labels; } int find_next_station(int s, int t, std::vector<int> c) { int case1 = 1; for (auto x: c) { if(s > x) { case1 = 0; break; } } if(case1) { /// par - tout /// s - tin /// kid - tout int par = -1; if(s != 0) { par = c.back(); c.pop_back(); } int ins = s, outs = s+1; vector < int > in, out; int kids = c.size(); for (auto x: c) out.pb(x); if(kids) { in.pb(s + 1); for (int i = 1; i < kids; ++ i) { in.pb(out[i-1] + 1); } outs = out.back() + 1; } for (int i = 0; i < kids; ++ i) { if(in[i] <= t && t <= out[i]) return out[i]; } return par; } else { /// tin /// tout /// tin int par = c[0]; int ins = s-1, outs = s; vector < int > in, out; for (int i = 1; i < c.size(); ++ i) in.pb(c[i]); int kids = in.size(); if(kids) { out.pb(s - 1); for (int i = kids-2; i >= 0; -- i) { out.pb(in[i+1] - 1); } reverse(out.begin(), out.end()); } for (int i = 0; i < kids; ++ i) { if(in[i] <= t && t <= out[i]) return in[i]; } return par; } } /** 2 7 10000000 0 1 0 2 0 6 2 3 2 4 3 5 4 6 3 0 4 1 2 3 4 2 4 3 2 7 10000000 0 1 0 2 0 6 2 3 2 4 3 5 4 6 3 0 1 3 0 3 4 2 4 3 2 */
#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...