제출 #422999

#제출 시각아이디문제언어결과실행 시간메모리
422999amoo_safar통행료 (IOI18_highway)C++17
51 / 100
294 ms13928 KiB
#include "highway.h" #include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; typedef long long ll; const int N = 2e5 + 10; int n, m; ll dis; vector<int> G[N], U, V; int bound; vector<int> vis; int mk[N]; void BFS(int u){ int adj; mk[u] = 1; vis.pb(u); int po = 0; while(po < (int) vis.size()){ for(int ed : G[ vis[po] ]){ if(ed >= bound) continue; adj = U[ed] ^ V[ed] ^ vis[po]; if(mk[adj]) continue; mk[adj] = 1; vis.pb(adj); } po++; } } int Solve(int u){ memset(mk, 0, sizeof mk); vis.clear(); BFS(u); reverse(vis.begin(), vis.end()); int sz = vis.size(); int lw = 0, hg = sz, mid; while(lw + 1 < hg){ mid = (lw + hg) >> 1; memset(mk, 0, sizeof mk); for(int i = 0; i < mid; i++) mk[vis[i]] = 1; vector<int> w; for(int i = 0; i < m; i++) w.pb(mk[U[i]] || mk[V[i]] || (i > bound)); if(ask(w) == dis) lw = mid; else hg = mid; } return vis[lw]; } void find_pair(int _n, vector<int> _U, vector<int> _V, int A, int B) { n = _n; U = _U; V = _V; m = U.size(); for(int i = 0; i < m; i++) G[U[i]].pb(i), G[V[i]].pb(i); vector<int> w(m, 0); dis = ask(w); { int lw = 0, hg = m; int mid; while(lw + 1 < hg){ mid = (lw + hg) >> 1; vector<int> as(mid, 0); as.resize(m, 1); if(ask(as) == dis) hg = mid; else lw = mid; } bound = lw; } int u = U[bound]; int v = V[bound]; answer(Solve(u), Solve(v)); // int M = U.size(); // for (int j = 0; j < 50; ++j) { // std::vector<int> w(M); // for (int i = 0; i < M; ++i) { // w[i] = 0; // } // long long toll = ask(w); // } // answer(0, N - 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...