Submission #98824

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