Submission #308627

#TimeUsernameProblemLanguageResultExecution timeMemory
308627silverfishStations (IOI20_stations)C++14
31.04 / 100
1073 ms1280 KiB
#include <bits/stdc++.h> #include "stations.h" using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }; struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; string _ARR_(int* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef pair<int, int> pii; #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) const int INF = 1e9 + 7; const int MxN = 2000; vector<int> adj[MxN]; int counter = 0; vector<int> tin, tout; void dfs(int v, int p){ tin[v] = counter++; for(int u : adj[v]){ if(u != p){ dfs(u, v); } } tout[v] = counter++; return; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { counter = 0; for(int i= 0; i <= n; i++) adj[i].clear(); tin.assign(n, -1); tout.assign(n, -1); for(int i = 0; i < n-1; i++){ adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); } dfs(0, 0); vector<int> labels(n); for(int i = 0; i < n; i++){ labels[i] = 2000*tin[i] + tout[i]; } return labels; } int in(int label) { return label / MxN; } int out(int label){ return label % MxN; } bool inside(int a, int b){ return in(a) <= in(b) && out(b) <= out(a); } int find_next_station(int s, int t, vector<int> c) { int p = -1; for(int cur : c){ if(inside(cur, s)) p = cur; } for(int cur : c){ if(inside(cur, t) && cur != p) return cur; } 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...