Submission #517207

#TimeUsernameProblemLanguageResultExecution timeMemory
517207Ai7081Stations (IOI20_stations)C++17
100 / 100
1004 ms928 KiB
#include <bits/stdc++.h> using namespace std; int cnt; vector<int> ret, sub; vector<vector<int>> adj; void dfs(int v, int p, bool ismax) { ret[v] = cnt; sub[v] = 1; cnt += (!ismax); for (auto to : adj[v]) { if (to == p) continue; dfs(to, v, !ismax); if (ismax) ret[v] += sub[to]; sub[v] += sub[to]; } cnt += ismax; return; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { adj.assign(n, vector<int>()); for (int i=0; i<n-1; i++) { adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } sub.assign(n, 0); ret.assign(n, 0); cnt = 0; dfs(0, 0, 0); return ret; } int find_next_station(int s, int t, vector<int> c) { bool ismax = (s > c[0]); if (ismax) { if (t > s) return c[0]; for (int i=1; i<(int)c.size(); i++) { if (t < c[i]) return c[i-1]; } return c[c.size()-1]; } else { if (t < s) return c[c.size()-1]; for (int i=c.size()-2; i>=0; i--) { if (t > c[i]) return c[i+1]; } //cout << "test " << c[0] << endl; return c[0]; } }
#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...