Submission #404320

#TimeUsernameProblemLanguageResultExecution timeMemory
404320AmineTrabelsiStations (IOI20_stations)C++14
10 / 100
1069 ms656 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; const int Mx = 1010; int timer = 0; int tin[Mx],tout[Mx]; void dfs(int node,int par,vector<int> &labels,vector<vector<int>> &tr){ tin[node] = timer++; for(auto i:tr[node]){ if(i != par){ dfs(i,node,labels,tr); } } tout[node] = timer++; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { vector<int> labels(n); vector<vector<int>> tr(n+1,vector<int>(0)); for (int i = 0; i < n-1; i++) { tr[u[i]].push_back(v[i]); tr[v[i]].push_back(u[i]); } dfs(0,-1,labels,tr); for(int i=0;i<n;i++){ labels[i] = tin[i]+tout[i]*1000; } return labels; } int find_next_station(int s, int t, vector<int> c) { int s_tin = s%1000, s_tout = s/1000; int t_tin = t%1000, t_tout = t%1000; // going from s to t // if s,t not in each other subtree return c.back() if(s_tin >= t_tin && s_tout <= t_tout){ return c.back(); } if(t_tin >= s_tin && t_tout <= s_tout){ for(auto p:c){ int p_tin = p%1000, p_tout = p/1000; if(t_tin >= p_tin && t_tout <= p_tout){ return p; } } } return c.back(); } // c sorted // small c deeper in the tree // big c high in tree // last c is parent
#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...