Submission #308697

#TimeUsernameProblemLanguageResultExecution timeMemory
308697silverfishStations (IOI20_stations)C++17
5 / 100
921 ms1144 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, in; void dfs(int v, int p, bool isIn){ in[v] = isIn; tin[v] = counter++; for(int u : adj[v]){ if(u != p){ dfs(u, v, !isIn); } } 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); in.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, 1); vector<int> labels(n); for(int i = 0; i < n; i++){ labels[i] = (in[i] ? tin[i] /2 : tout[i]/2); } debug() << exp(labels); return labels; } int find_next_station(int s, int t, vector<int> c) { bool isFirst = 0; int p = -1; int len = (int)c.size(); sort(c.begin(), c.end()); if(s < c[0]) { p = c[len-1]; isFirst = 1; }else p = c[0]; debug() << exp(s) << exp(t) << exp(c) << exp(isFirst) << exp(p); if(len == 1){ return (s == t ? s : c[0]); } if(isFirst){ if(t < s || t > c[len-2]) return p; if(t > s && t <= c[0]) return c[0]; for(int i = 1; i < len-1; i++){ if(t <= c[i] && t > c[i-1]) return c[i]; } }else{ if(t > s || t < c[1]) return p; if(t < s && t >= c[len-1]) return c[len-1]; for(int i = 1; i < len-1; i++){ if(t >= c[i] && t > c[i+1]) return c[i]; } } return -1; }
#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...