Submission #831890

#TimeUsernameProblemLanguageResultExecution timeMemory
831890JasonweiStations (IOI20_stations)C++14
100 / 100
803 ms724 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; vector <vector <int> > g; int cnt; vector <int> labels; void dfs (int x, int fa, bool b) { if (b) labels[x] = cnt ++; for (int t : g[x]) { if (t == fa) continue; dfs (t, x, ! b); } if (! b) labels[x] = cnt ++; } vector <int> label (int n, int k, vector <int> u, vector<int> v) { cnt = 0; g.clear (), g.resize (n); for (int i = 0; i < n - 1; i++) g[u[i]].push_back (v[i]), g[v[i]].push_back (u[i]); labels.assign (n, -1); dfs (0, -1, true); return labels; } int find_next_station (int s, int t, vector <int> c) { int n = (int) c.size (); if (s < c[0]) { if (t < s) return c[n - 1]; for (int i = 0; i < n - 1; i ++) { if (t <= c[i]) return c[i]; } return c[n - 1]; } else { if (t > s) return c[0]; for (int i = n - 1; i > 0; i --) { if (c[i] <= t) return c[i]; } 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...