Submission #799447

#TimeUsernameProblemLanguageResultExecution timeMemory
799447Sohsoh84Highway Tolls (IOI18_highway)C++17
23 / 100
588 ms42516 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define sep ' ' #define debug(x) cerr << #x << ": " << x << endl; #define all(x) (x).begin(), (x).end() const int MAXN = 1e6 + 10; bool bad[MAXN]; int askcnt = 0; int from[MAXN], to[MAXN], n, m, par[MAXN], mn; vector<int> adj[MAXN], dfs_order, fuck, jahel; int fucking_root, A, B; inline int f(int ind, int v) { return from[ind] ^ to[ind] ^ v; } void dfs(int v, int p, int d = 0) { dfs_order.push_back(v); if (d == mn / A) jahel.push_back(v); for (int ind : adj[v]) { int u = f(ind, v); if (u == p) continue; if (bad[u]) continue; par[u] = ind; dfs(u, v, d + 1); } } inline vector<int> seg(int l, int r) { vector<int> ans; for (int i = l; i <= r; i++) ans.push_back(par[dfs_order[i]]); return ans; } inline int get(vector<int> vec) { askcnt++; assert(askcnt <= 90); vector<int> W(m); for (int i = 0; i < m; i++) W[i] = 1; for (int e : fuck) W[e] = 0; for (int e : vec) W[e] = 1; return ask(W); } inline int getp(vector<int> vec) { askcnt++; assert(askcnt <= 90); vector<int> W(m); for (int i = 0; i < m; i++) W[i] = 1; for (int e : vec) W[e] = 0; return ask(W); } inline int get(int l, int r) { return get(seg(l, r)); } inline int getp(int l, int r) { return getp(seg(l, r)); } inline int find(int root, int tof = 0) { par[root] = -1; dfs_order.clear(); jahel.clear(); dfs(root, root); debug(root) jahel.insert(jahel.begin(), 0); int l = 1, r = int(dfs_order.size()) - 1; if (tof) r = int(jahel.size()) - 1; for (int e : dfs_order) cerr << e << sep; cerr << endl; while (l < r) { int mid = (l + r) >> 1; int tmid = mid; if (tof) { tmid = 1; while (dfs_order[tmid] != jahel[mid]) tmid++; } if (getp(1, tmid) == mn) r = mid; else l = mid + 1; } return (tof ? jahel[l] : dfs_order[l]); } int dist[MAXN]; const double Z = 0.45; inline vector<int> random_spt() { vector<int> ans; queue<int> q; int l = 0, r = n - 1; while (l < r) { int len = r - l; int mid = l + Z * len; mid = max(mid, l); mid = min(mid, r - 1); vector<int> W(m); for (int i = 0; i < m; i++) if (from[i] <= mid || to[i] <= mid) W[i] = 1; if (ask(W) == mn) { for (int i = l; i <= mid; i++) bad[i] = true; l = mid + 1; } else r = mid; } int v = l; fucking_root = v; memset(dist, 63, sizeof dist); q.push(v); dist[v] = 0; while (!q.empty()) { int v = q.front(); q.pop(); if (v < fucking_root) continue; for (int ind : adj[v]) { int u = f(ind, v); if (u < fucking_root) continue; if (dist[u] > dist[v] + 1) { dist[u] = dist[v] + 1; q.push(u); ans.push_back(ind); } } } return ans; } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A_, int B_) { m = U.size(); n = N; A = A_; B = B_; for (int i = 0; i < m; i++) { from[i] = U[i]; to[i] = V[i]; adj[from[i]].push_back(i); adj[to[i]].push_back(i); } for (int i = 0; i < m; i++) fuck.push_back(i); mn = get({}); vector<int> tmp = random_spt(); fuck = tmp; for (int i = 0; i < n; i++) adj[i].clear(); for (int ind : tmp) { adj[from[ind]].push_back(ind); adj[to[ind]].push_back(ind); } int v = find(fucking_root); int u = find(v, 1); cerr << u << sep << v << endl; answer(u, v); }
#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...