Submission #308157

#TimeUsernameProblemLanguageResultExecution timeMemory
308157jwvg0425Stations (IOI20_stations)C++17
36.32 / 100
1043 ms1128 KiB
#include "stations.h" #include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; template<typename T, typename Pr = less<T>> using pq = priority_queue<T, vector<T>, Pr>; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; struct Solver { vector<int> edge[1005]; int in[1005] = { 0, }, out[1005] = { 0, }; int vis = 0; void dfs(int root) { in[root] = vis; vis++; for (auto& e : edge[root]) { edge[e].erase(find(all(edge[e]), root)); dfs(e); } out[root] = vis; } }; vector<int> label(int n, int k, vector<int> u, vector<int> v) { Solver s; for (int i = 0; i < n - 1; i++) { s.edge[u[i]].push_back(v[i]); s.edge[v[i]].push_back(u[i]); } s.dfs(0); vector<int> res(n); for (int i = 0; i < n; i++) res[i] = s.in[i] * 1001 + s.out[i]; return res; } int find_next_station(int s, int t, vector<int> c) { int ti = t / 1001; int to = t % 1001; int si = s / 1001; int so = s % 1001; int p = c[0]; for (auto& e : c) { int ei = e / 1001; int eo = e % 1001; if (ei <= si && eo >= so) { p = e; continue; } if (ei <= ti && eo >= to) return e; } return p; }
#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...