Submission #1240269

#TimeUsernameProblemLanguageResultExecution timeMemory
1240269Ghulam_JunaidStations (IOI20_stations)C++17
0 / 100
3056 ms2162688 KiB
#include <bits/stdc++.h> #include "stations.h" // #include "stub.cpp" using namespace std; const int N = 1e3 + 10; int sz[N]; vector<int> res, g[N]; void dfs(int v, int p = -1){ sz[v] = 1; for (int u : g[v]){ if (u == p) continue; dfs(u, v); sz[v] += sz[u]; } } void assign(int v, int l = 0, int r = sz[0], int p = -1){ if (p == -1 or res[p] == l) res[v] = l + sz[v]; else res[v] = l + 1; int prv = 0; for (int u : g[v]){ if (u == p) continue; if (res[v] == l + 1) assign(u, l + 1 + prv, r, v); else assign(u, l + prv, r - 1, v); prv += sz[u]; } } vector<int> label(int n, int k, vector<int> u, vector<int> v) { res.resize(n); for (int i = 0; i < n - 1; i ++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } dfs(0); assign(0); return res; } int find_next_station(int s, int t, vector<int> c) { if (c.size() == 1) return c[0]; if (s < c[0]){ if (t < s) return c.back(); } else{ if (t > s) return c[0]; } int ind = upper_bound(c.begin(), c.end(), t) - c.begin() - 1; return c[ind]; }
#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...