Submission #817827

#TimeUsernameProblemLanguageResultExecution timeMemory
817827pavementHighway Tolls (IOI18_highway)C++17
51 / 100
137 ms35580 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define mt make_tuple using ll = long long; using ii = pair<int, int>; int ed; vector<int> ndep; vector<vector<int> > U_edges, V_edges; vector<vector<ii> > adj; void dfs(int u, vector<vector<int> > &edges, int dep = 0, int e = -1) { ndep[u] = dep; for (auto [v, idx] : adj[u]) if (v != e && idx != ed) { edges[dep].pb(idx); dfs(v, edges, dep + 1, u); } } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { ndep.resize(N); adj.resize(N); int M = (int)U.size(); vector<int> cur; for (int i = 0; i < M; i++) { adj[U[i]].eb(V[i], i); adj[V[i]].eb(U[i], i); cur.pb(i); } ll original = ask(vector<int>(M, 0)); while ((int)cur.size() > 1) { vector<int> w(M, 0); for (int i = 0; i < (int)cur.size() / 2; i++) { w[cur[i]] = 1; } if (ask(w) > original) { int new_sz = (int)cur.size() / 2; while ((int)cur.size() != new_sz) cur.pop_back(); } else { int new_sz = ((int)cur.size() + 1) / 2; reverse(cur.begin(), cur.end()); while ((int)cur.size() != new_sz) cur.pop_back(); reverse(cur.begin(), cur.end()); } } ed = cur[0]; U_edges.resize(N); V_edges.resize(N); dfs(U[ed], U_edges); dfs(V[ed], V_edges); vector<int> w(M, 0); for (auto edges_by_dep : U_edges) { for (auto edge : edges_by_dep) { w[edge] = 1; } } ll tmp = ask(w); int U_len = (tmp - original) / (B - A); int V_len = original / A - U_len - 1; int S, T; for (auto [len, edges, R, W] : {mt(U_len, U_edges, &S, U), mt(V_len, V_edges, &T, V)}) { if (len) { vector<int> cur = edges[len - 1]; while ((int)cur.size() > 1) { vector<int> w(M, 0); for (int i = 0; i < (int)cur.size() / 2; i++) { w[cur[i]] = 1; } if (ask(w) > original) { int new_sz = (int)cur.size() / 2; while ((int)cur.size() != new_sz) cur.pop_back(); } else { int new_sz = ((int)cur.size() + 1) / 2; reverse(cur.begin(), cur.end()); while ((int)cur.size() != new_sz) cur.pop_back(); reverse(cur.begin(), cur.end()); } } *R = (ndep[U[cur[0]]] > ndep[V[cur[0]]] ? U[cur[0]] : V[cur[0]]); } else { *R = W[ed]; } } answer(S, T); }
#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...