Submission #996720

#TimeUsernameProblemLanguageResultExecution timeMemory
996720phoenixStations (IOI20_stations)C++17
0 / 100
3049 ms2097152 KiB
#include "stations.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; const int N = 1010; int T; int tin[N]; int tout[N]; vector<int> g[N]; void precalc(int s, int p) { tin[s] = T++; for (int to : g[s]) if (to != p) precalc(to, s); tout[s] = T++; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { for (int i = 0; i < n - 1; i++) { g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } vector<int> labels(n); precalc(0, 0); for (int i = 0; i < n; i++) if (tin[i] & 1) labels[i] = tout[i]; else labels[i] = tin[i]; // for (int i = 0; i < n; i++) // cout << labels[i] << ' '; // cout << '\n'; return labels; } int find_next_station(int s, int t, vector<int> c) { if ((int)c.size() == 1) return c[0]; int m = (int)c.size(); sort(c.begin(), c.end()); if (!s) { int prev = s; pair<int, int> nxt[m]; for (int i = 0; i < m; i++) { nxt[i].first = prev + 1; nxt[i].second = c[i]; prev = nxt[i].second; } for (int i = 0; i < m; i++) { if (nxt[i].first <= t && t <= nxt[i].second) return c[i]; } } if (s < c[0]) { int prev = s; for (int i = 0; i < m - 1; i++) { int l = prev + 1; int r = c[i]; prev = r; if (l <= t && t <= r) return c[i]; } return c.back(); } reverse(c.begin(), c.end()); int prev = s; for (int i = 0; i < m - 1; i++) { int l = c[i]; int r = prev; prev = c[i] - 1; if (l <= t && t <= r) return c[i]; } return c.back(); }
#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...