Submission #308616

#TimeUsernameProblemLanguageResultExecution timeMemory
308616silverfishStations (IOI20_stations)C++14
0 / 100
888 ms768 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 = 1001; vector<int> adj[MxN]; int counter = 0; int tin[MxN], tout[MxN]; 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 = -1; memset(tin, 0, sizeof tin); memset(tout, 0, sizeof tout); for(int i= 0; i <= n; i++) adj[i].clear(); 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 find_next_station(int s, int t, vector<int> c) { //debug() << exp(s) << exp(t) << exp(c); int s1 = s/2000, s2 = s % 2000; int t1 = t/2000, t2 = t % 2000; //debug() << exp(s1) << exp(s2) << exp(t1) << exp(t2); int p = 0, ans = 0; bool foundRange = 0; int best1 = -INF, best2 = INF; for(int cur : c){ int c1 = cur/2000, c2 = cur % 2000; // debug() << exp(c1) << exp(c2); if(c1 < s1 && c2 > s2) p = cur; if(c1 < t1 && c2 > t2 && (c1 > best1 && c2 < best2)) { foundRange = 1; best1 = c1; best2 = c2; ans = cur; } } if(!foundRange) ans = p; return ans; }
#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...