Submission #98893

#TimeUsernameProblemLanguageResultExecution timeMemory
98893Just_Solve_The_ProblemHighway Tolls (IOI18_highway)C++11
100 / 100
980 ms46172 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, s, t; 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; } int u, v; u = U[r]; v = V[r]; queue < int > q; q.push(u); q.push(v); addedge(u, v); connect(u, v); w[r] = 0; 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); vector < int > ord; for (int i = 0; i < n; i++) { for (int to : vec[i]) { ord.push_back(to); } vec[i].clear(); } l = -1; r = ord.size() - 1; while (r - l > 1) { int mid = (l + r) >> 1; for (int i = 0; i <= mid; i++) { w[idc[ord[i]]] = 0; } ll T = ask(w); for (int i = 0; i <= mid; i++) { w[idc[ord[i]]] = 1; } if (T == dist * A) { r = mid; } else { l = mid; } } s = ord[r]; ord.clear(); h[v] = 0; for (int to : del) { w[to] = 0; } del.clear(); dfs(v, u); for (int i = 0; i < n; i++) { for (int to : vec[i]) { ord.push_back(to); } } l = -1; r = ord.size(); while (r - l > 1) { int mid = (l + r) >> 1; for (int i = 0; i <= mid; i++) { w[idc[ord[i]]] = 0; } ll T = ask(w); for (int i = 0; i <= mid; i++) { w[idc[ord[i]]] = 1; } if (T == dist * A) { r = mid; } else { l = mid; } } t = ord[r]; answer(s, t); } /* 8 10 1 2 0 2 0 1 0 2 0 3 1 4 0 5 5 6 2 7 2 3 3 6 5 7 */
#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...