제출 #342894

#제출 시각아이디문제언어결과실행 시간메모리
342894cki86201통행료 (IOI18_highway)C++17
51 / 100
407 ms11192 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; #define Fi first #define Se second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(), (x).end() #define pb push_back #define szz(x) (int)(x).size() #define rep(i, n) for(int i=0;i<(n);i++) typedef tuple<int, int, int> t3; vector <int> EV; vector <pii> E[100010]; int dv[2][100010]; void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int M = szz(U); rep(i, M) E[U[i]].pb({V[i], i}), E[V[i]].pb({U[i], i}); EV.resize(M); ll dist = ask(EV); int low = 0, high = M - 1; while(low < high) { int mid = (low + high) >> 1; rep(i, M) EV[i] = (low <= i && i <= mid); if(ask(EV) != dist) high = mid; else low = mid + 1; } int P = U[low], Q = V[low]; rep(u, 2) { int st = (u ? Q : P); vector <int> q; q.pb(st); rep(i, N) dv[u][i] = -1; dv[u][st] = 0; rep(i, szz(q)) { int t = q[i]; for(auto [e, _] : E[t]) if(dv[u][e] == -1) { dv[u][e] = dv[u][t] + 1; q.pb(e); } } } auto Find = [&](int P, vector <int> &C, int dis[]) { sort(all(C), [&](int x, int y) { return dis[x] < dis[y]; }); int low = 0, high = szz(C) - 1; while(low < high) { int mid = (low + high) >> 1; rep(i, M) EV[i] = 0; for(int i=mid+1;i<szz(C);i++) { int x = C[i]; for(auto [e, id] : E[x]) { if(dis[e] + 1 == dis[x]) EV[id] = 1; } } if(ask(EV) != dist) low = mid + 1; else high = mid; } return C[low]; }; vector <int> R[2]; rep(i, N) { if(dv[0][i] < dv[1][i]) R[0].pb(i); if(dv[0][i] > dv[1][i]) R[1].pb(i); } answer(Find(P, R[0], dv[0]), Find(Q, R[1], dv[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...
#Verdict Execution timeMemoryGrader output
Fetching results...