Submission #604661

#TimeUsernameProblemLanguageResultExecution timeMemory
604661PiejanVDCHighway Tolls (IOI18_highway)C++17
18 / 100
401 ms46436 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; const int mxN = (int)9e4+5; int def; long long normal; int N_; mt19937 mt(time(nullptr)); 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; ans = mid; } else l = mid+1; } return points[r]; } 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-1; 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; } void delete_(int a) { if(a == def) return; for(int i = 0 ; i <= mxDist ; i++) p[i].clear(); stack<int>s; s.push(a); vector<bool>vis(N_+1, 0); vis[a] = 1; while(1) { int node = s.top(); s.pop(); for(auto z : adj[node]) if(!vis[z]) { if(z == def) { h = node; return; } vis[z] = 1; s.push(z); } } } 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<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], 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; def = rev[search_point(d)]; dfs(def, 0); int a = distance(); if(a == -1) A_ = def; else { A_ = search_point(p[a]); A_ = (re[u[A_]] > re[v[A_]] ? u[A_] : v[A_]); } delete_(A_); mxDist = 0; dfs(def, 0); long long need = normal / a_ - max(0, a); int b = need; int B_ = -1; if(b == 0) B_ = def; else { B_ = search_point(p[b]); B_ = (re[u[B_]] > re[v[B_]] ? u[B_] : v[B_]); } answer(A_, B_); }

Compilation message (stderr)

highway.cpp: In function 'int search_point(std::vector<int>)':
highway.cpp:19:9: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   19 |     int ans = -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...