제출 #162818

#제출 시각아이디문제언어결과실행 시간메모리
162818Minnakhmetov통행료 (IOI18_highway)C++14
51 / 100
410 ms262148 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define ll long long struct E { int to, i; }; const int N = 1e5 + 5; vector<E> g[N], ord; int anc[N]; void dfs(int node) { for (E e : g[node]) { if (e.to != anc[node]) { ord.push_back(e); anc[e.to] = node; dfs(e.to); } } } void find_pair(int n, vector<int> u, vector<int> v, int a, int b) { int m = u.size(); for (int i = 0; i < m; i++) { g[u[i]].push_back({v[i], i}); g[v[i]].push_back({u[i], i}); } ll dist = ask(vector<int>(m, 0)) / a; dfs(0); // for (E e : ord) { // cout << e.to << " "; // } // cout << "\n"; int s, t; int l = -1, r = ord.size() - 1; while (r - l > 1) { int p = (l + r) >> 1; vector<int> w(m); for (int i = 0; i <= p; i++) w[ord[i].i] = 1; if (ask(w) == dist * b) r = p; else l = p; } s = ord[r].to; l = -1, r = ord.size() - 1; while (r - l > 1) { int p = (l + r) >> 1; vector<int> w(m); for (int i = 0; i <= p; i++) w[ord[i].i] = 1; if (ask(w) > dist * a) r = p; else l = p; } int lca = anc[ord[r].to]; // cout << lca << " " << s << "\n"; int x = s; ll half = 0; while (x != lca) { half++; x = anc[x]; } if (half == dist) { t = lca; } else { l = -1, r = ord.size() - 1; while (r - l > 1) { int p = (l + r) >> 1; vector<int> w(m); for (int i = 0; i <= p; i++) w[ord[i].i] = 1; if (ask(w) >= dist * a + (dist - half) * (b - a)) r = p; else l = p; } t = ord[r].to; } 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...