제출 #594997

#제출 시각아이디문제언어결과실행 시간메모리
594997MadokaMagicaFan기지국 (IOI20_stations)C++14
0 / 100
3031 ms2097152 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define all(v) v.begin(),v.end() #define sort(v) sort(all(v)) #define endl '\n' #define forn(i,n) for(int i = 0; i < n; ++i) #define forbe(i,b,e) for(int i = b; i < e; ++i) #define forr(i,n) for(int i = n-1; i >= 0; --i) #define sz(v) ((int)v.size()) #define pb push_back #define f first #define s second const int N = 1e3; vi adj[N]; bitset<N> bip; vi ret; int cnt; void dfs(int x, int p) { if (!bip[x]) ret[x] = cnt++; for(int u : adj[x]) { if (u == p) continue; bip[u] = !bip[x]; dfs(u, x); } if (bip[x]) ret[x] = cnt++; } vi label(int n, int k, vi u, vi v) { cnt = 0; forn(i ,n-1) { adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); } ret.assign(n,0); dfs(0,0); return ret; } int find_next_station(int s, int t, vi c) { if (s == t) return s; if (sz(c) == 1) return c[0]; int mn, mx; mn = N; mx = 0; int p; for (int u : c) { mn = min(u, mn); mx = max(u, mx); } sort(c); if (mx > s) { p = mx; if (t < s) return p; if (t >= p) return p; reverse(all(c)); forn(i, sz(c)) { if (c[i] < t) return c[i-1]; } return c[sz(c)-1]; } else { p = mn; if (t > s) return p; if (t <= p) return p; forn(i, sz(c)) { if (c[i] > t) return c[max(i-1,0)]; } return c[sz(c)-1]; } } #ifdef ONPC void solve() { int n,k; cin >> n >> k; vi u(n-1), v(n-1); forn(i,n-1) cin >> u[i] >> v[i]; vi l = label(n, k, u, v); forn(i, n) cout << l[i] << ' '; cout << endl; //return; int q; cin >> q; while (q--) { int a, b; cin >> a >> b; vi c; for(int u : adj[a]) c.pb(l[u]); cout << find_next_station(l[a], l[b], c) << endl; } } int main() { freopen("in", "r", stdin); // ios_base::sync_with_stdio(0);cin.tie(0); solve(); } #endif
#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...