Submission #738150

#TimeUsernameProblemLanguageResultExecution timeMemory
738150PixelCatHighway Tolls (IOI18_highway)C++14
100 / 100
253 ms11924 KiB
#ifdef NYAOWO #include "grader.cpp" #endif #include "highway.h" #include <bits/stdc++.h> #define For(i, a, b) for(int i = a; i <= b; i++) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define eb emplace_back using namespace std; using LL = long long; using pii = pair<int, int>; const int MAXN = 90010; vector<pii> adj[MAXN]; // index, eid int dep[MAXN]; int eid[MAXN]; int typ[MAXN]; void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { cerr << A << " " << B << "\n"; int M = U.size(); LL dist = ask(vector<int>(M, 0)); assert(dist % A == 0); auto out = [&](int x) { cerr << "(" << U[x] << ", " << V[x] << ")\n" << flush; }; For(i, 0, M - 1) { adj[U[i]].eb(V[i], i); adj[V[i]].eb(U[i], i); } int hi = M - 1, lo = -1; while(hi - lo > 1) { int mi = lo + (hi - lo) / 2; vector<int> w(M, 0); fill(w.begin(), w.begin() + mi + 1, 1); LL d2 = ask(w); if(d2 > dist) hi = mi; else lo = mi; } int a = U[hi], b = V[hi]; cerr << "key edge: " << hi << " "; out(hi); // build bfs tree memset(typ, -1, sizeof(typ)); queue<int> que; dep[a] = 1; dep[b] = 1; eid[a] = eid[b] = hi; typ[a] = 0; typ[b] = 1; que.emplace(a); que.emplace(b); vector<int> ed[2]; vector<int> w0(M, 1); while(!que.empty()) { int cur = que.front(); que.pop(); w0[eid[cur]] = 0; ed[typ[cur]].eb(eid[cur]); for(auto &e:adj[cur]) if(typ[e.F] == -1 && e.S >= hi) { dep[e.F] = dep[cur] + 1; eid[e.F] = e.S; typ[e.F] = typ[cur]; que.emplace(e.F); } } // cerr << "bfs tree #0\n"; for(auto &id:ed[0]) out(id); // cerr << "bfs tree #1\n"; for(auto &id:ed[1]) out(id); int m = sz(ed[0]); hi = m; lo = -1; while(hi - lo > 1) { int mi = lo + (hi - lo) / 2; vector<int> w(all(w0)); For(i, mi, m - 1) w[ed[0][i]] = 1; auto d2 = ask(w); if(d2 == dist) hi = mi; else lo = mi; } dep[b] = 0; int id = ed[0][lo]; int x0 = U[id]; if(dep[V[id]] > dep[U[id]]) x0 = V[id]; cerr << "x0: " << x0 << "\n"; dep[b] = 1; m = sz(ed[1]); hi = m; lo = -1; while(hi - lo > 1) { int mi = lo + (hi - lo) / 2; vector<int> w(all(w0)); For(i, mi, m - 1) w[ed[1][i]] = 1; auto d2 = ask(w); if(d2 == dist) hi = mi; else lo = mi; } dep[a] = 0; id = ed[1][lo]; int x1 = U[id]; if(dep[V[id]] > dep[U[id]]) x1 = V[id]; cerr << "x1: " << x1 << "\n"; dep[a] = 1; answer(x0, x1); // 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); } /* 4 4 1 3 1 3 0 1 0 2 0 3 1 2 */
#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...