Submission #1240307

#TimeUsernameProblemLanguageResultExecution timeMemory
1240307Ghulam_JunaidStations (IOI20_stations)C++17
100 / 100
306 ms588 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 = 1, int p = -1, int dist = 0){ if (dist % 2 == 0) res[v] = l + sz[v] - 1; else res[v] = l; // cout << v << " : " << res[v] << endl; int prv = 0; for (int u : g[v]){ if (u == p) continue; assign(u, l + (res[v] == l) + prv, v, dist + 1); 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; i ++) g[i].clear(); 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]){ // I am the one who says everyone in subtree is >= s if (t < s or t > c[c.size() - 2]) return c.back(); return *lower_bound(c.begin(), c.end(), t); } else{ // <= s if (t > s or t < c[1]) return c[0]; return c[upper_bound(c.begin(), c.end(), t) - c.begin() - 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...