Submission #607377

#TimeUsernameProblemLanguageResultExecution timeMemory
607377PiejanVDCHighway Tolls (IOI18_highway)C++17
0 / 100
19 ms10740 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; const int mxN = (int)9e4+5; int def; long long normal; int N_; long long ask(const std::vector<int> &w); void answer(int s, int t); map<pair<int,int>, int>id; vector<int>re(mxN); int search_point(vector<int>points) { int n = (int)points.size(); int ans = -1; int l = 0, r = n-1; while(l <= r) { int mid = (l+r)/2; vector<int>Ask(N_, 0); for(int i = l ; i < mid ; i++) Ask[points[i]] = 1; if(ask(Ask) != normal) { r = mid-2; ans = mid; } else l = mid; } return points[ans]; } bool present(vector<int>points) { vector<int>Ask(N_, 0); for(auto z : points) Ask[z] = 1; return ask(Ask) != normal; } vector<int>p[mxN]; vector<int>parent(mxN); vector<int>adj[mxN]; int mxDist; int A_ = -2; int h = -2; void dfs(int node, int dist, int e = -1) { if(node == h) return; mxDist = max(mxDist, dist); if(e > -1) p[dist].push_back(id[{node, e}]); parent[node] = e; re[node] = dist; for(auto z : adj[node]) if(z != e) dfs(z, dist+1, node); } int distance() { int l = 1, r = mxDist; int ans = -1; while(l <= r) { int mid = (l+r)/2; if(present(p[mid])) ans = mid, l = mid+1; else r = mid-1; } return ans; } int Check = 1; void check() { /*cout << "Check " << Check++ << '\n';*/ } void find_pair(int n, vector<int>u, vector<int>v, int a_, int b_) { N_ = n-1; vector<int>dummy(n-1, 0); normal = ask(dummy); vector<pair<int,int>>rev(n-1); for(int i = 0 ; i < n-1 ; i++) id[{u[i], v[i]}] = id[{v[i], u[i]}] = i, rev[i] = {u[i],v[i]}, adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]); vector<int>d(n-1); for(int i = 0 ; i < n-1 ; i++) d[i] = i; auto [f,s] = rev[search_point(d)]; dfs(f, 0, s); int a = distance(); if(a == -1) A_ = f; else { A_ = search_point(p[a]); A_ = (re[u[A_]] > re[v[A_]] ? u[A_] : v[A_]); } for(int i = 0 ; i <= mxDist ; i++) p[i].clear(); mxDist = 0; dfs(s, 0, f); int b = normal / a_ - max(0,a) - 1; int B_ = -1; if(!b) B_ = s; else { B_ = search_point(p[b]); B_ = (re[u[B_]] > re[v[B_]] ? u[B_] : v[B_]); } answer(A_, B_); }
#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...