제출 #835083

#제출 시각아이디문제언어결과실행 시간메모리
835083welleyth기지국 (IOI20_stations)C++17
0 / 100
3039 ms2097152 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; constexpr int N = (int)2e3 + 1; int tin[N],tout[N]; int timer = 0; vector<int> g[N]; mt19937 rnd(time(nullptr)); void dfs(int v,int pr = -1){ tin[v] = timer++; for(auto& to : g[v]){ if(to == pr) continue; dfs(to,v); } tout[v] = timer++; return; } std::vector<int> label(int n, int k, std::vector<int> u, std::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]); } dfs(0); vector<int> labels(n); for(int i = 0; i < n; i++){ labels[i] = tin[i] * N + tout[i]; } return labels; } bool upper(int tinA,int toutA,int tinB,int toutB){ return tinA <= tinB && toutA >= toutB; } int find_next_station(int s, int t, std::vector<int> c) { int tinS = s / N, toutS = s % N; int tinT = t / N, toutT = t % N; int pr = 0; for(auto& to : c){ int tin = to / N, tout = to % N; if(upper(tin,tout,tinS,toutS)){ pr = to; continue; } if(upper(tin,tout,tinT,toutT)) return to; } return pr; }
#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...