Submission #98847

#TimeUsernameProblemLanguageResultExecution timeMemory
98847Just_Solve_The_ProblemHighway Tolls (IOI18_highway)C++11
51 / 100
798 ms45504 KiB
#include "highway.h" // #include "grader.cpp" #include <vector> #include <map> #include <utility> #include <iostream> #include <queue> #define ll long long using namespace std; const int maxn = (int)2e5 + 7; vector < int > gr[maxn]; vector < int > nwgr[maxn]; vector < int > vec[maxn]; vector < int > w; vector < int > del; map < pair < int, int >, int > mp; int id[maxn], h[maxn], p[maxn], idc[maxn]; int get(int a) { if (id[a] == a) return a; return id[a] = get(id[a]); } void connect(int a, int b) { a = get(a); b = get(b); id[a] = b; } void addedge(int a, int b) { nwgr[a].push_back(b); nwgr[b].push_back(a); } void dfs(int v, int pr) { vec[h[v]].push_back(v); p[v] = pr; idc[v] = mp[{v, pr}]; for (int to : nwgr[v]) { if (to == pr) continue; h[to] = h[v] + 1; del.push_back(mp[{v, to}]); w[del.back()] = 1; dfs(to, v); } } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int n = N; int m = U.size(); ll dist = 0; w.resize(m, 0); dist = ask(w) / A; for (int i = 0; i < n; i++) { id[i] = i; } for (int i = 0; i < m; i++) { int u, v; u = U[i]; v = V[i]; mp[{v, u}] = mp[{u, v}] = i; gr[u].push_back(v); gr[v].push_back(u); } int l = -1; int r = m - 1; while (r - l > 1) { int mid = (l + r) >> 1; for (int i = 0; i <= mid; i++) { w[i] = 1; } ll T = ask(w); for (int i = 0; i <= mid; i++) { w[i] = 0; } if (T == dist * A) { l = mid; } else { r = mid; } } for (int i = 0; i < m; i++) { w[i] = 1; } w[r] = 0; int u, v; u = U[r]; v = V[r]; queue < int > q; q.push(u); q.push(v); addedge(u, v); connect(u, v); while (!q.empty()) { int asd = q.front(); q.pop(); for (int to : gr[asd]) { if (get(to) != get(asd)) { addedge(asd, to); connect(asd, to); w[mp[{asd, to}]] = 0; q.push(to); } } } dfs(u, v); ll asd = (ask(w) - dist * A) / (B - A); for (int to : del) { w[to] = 0; } del.clear(); l = -1; r = vec[asd].size() - 1; while (r - l > 1) { int mid = (l + r) >> 1; for (int i = 0; i <= mid; i++) { int v = vec[asd][i]; w[idc[v]] = 1; } ll T = ask(w); for (int i = 0; i <= mid; i++) { int v = vec[asd][i]; w[idc[v]] = 0; } if (T == dist * A) { l = mid; } else { r = mid; } } int s, t; s = vec[asd][r]; for (int i = 0; i < n; i++) { vec[i].clear(); } h[s] = 0; dfs(s, s); for (int to : del) { w[to] = 0; } asd = dist; l = -1; r = vec[asd].size() - 1; while (r - l > 1) { int mid = (l + r) >> 1; for (int i = 0; i <= mid; i++) { int v = vec[asd][i]; w[idc[v]] = 1; } ll T = ask(w); for (int i = 0; i <= mid; i++) { int v = vec[asd][i]; w[idc[v]] = 0; } if (T == dist * A) { l = mid; } else { r = mid; } } t = vec[asd][r]; answer(s, t); } /* 7 7 4 5 4 6 0 2 0 5 1 2 2 3 3 4 4 5 4 6 4 4 3 4 2 3 0 1 1 2 2 3 3 0 */
#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...