Submission #785362

#TimeUsernameProblemLanguageResultExecution timeMemory
785362drdilyorHighway Tolls (IOI18_highway)C++17
51 / 100
285 ms262144 KiB
#include <bits/stdc++.h> #include "highway.h" #ifdef ONPC #include "t_debug.cpp" #else #define debug(...) 42 #endif using namespace std; //namespace pbds = __gnu_pbds; using ll = long long; const int inf = 1e9; const ll infl = 1e18; const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rng(RANDOM); template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; } template<typename Cont> int sz(const Cont& cont) { return int(cont.size()); } template<typename Func> struct ycom { Func f; template<typename... T> auto operator()(T&&... args) { return f(*this, args...); } }; template<typename Func> ycom(Func) -> ycom<Func>; template<typename T> typename vector<T>::iterator operator+(const vector<T>& x, int i) { return x.begin() + i ;}; const string fileio = ""; constexpr int tests = 1, nmax = 2e5, nlog = __lg(nmax), mod = 1e9+7; void find_pair(int32_t n, std::vector<int32_t> u, std::vector<int32_t> v, int32_t a, int32_t b) { int m = u.size(); vector<vector<pair<int,int>>> adj(n); for (int i = 0; i < m; i++) { adj[u[i]].emplace_back(v[i], i); adj[v[i]].emplace_back(u[i], i); } ll base = ask(vector(m, 0)); int len = base / a; auto mark_subtree = [&](auto& dfs, vector<int>& w, int i, int p)->void{ for (auto[e, ei] : adj[i]) { if (e == p) continue; w[ei] = 1; dfs(dfs, w, e, i); } }; auto find_path_from_root = [&](int root, int p, int len) { if (len == 0) { return root; } vector<pair<int,int>> level; auto dfs = [&](auto& dfs, int i, int p, int dep)->void{ for (auto [e, ei] : adj[i]) { if (e == p) continue; if (dep+1 == len) { level.emplace_back(e, ei); continue; } dfs(dfs, e, i, dep+1); } }; dfs(dfs, root, p, 0); int l = 0, r = level.size()-1; while (l < r) { int mid = (l + r) / 2; vector<int> w(m); for (int i = l; i <= mid; i++) { w[level[i].second] = 1; } ll toll = ask(w); assert(toll == base || toll == base - a + b); if (toll == base) { l = mid+1; } else r = mid; } return level[l].first; }; int l = 0, r = m-1; while (l < r) { int mid = (l + r) / 2; vector<int> w(m); fill(w.begin() + l, w.begin() + mid+1, 1); ll toll = ask(w); if (toll == base) l = mid+1; else r = mid; } int left = u[l]; int right = v[l]; vector<int> w(m); mark_subtree(mark_subtree, w, left, right); int left_len = (ask(w) - base) / (b - a); answer( find_path_from_root(left, right, left_len), find_path_from_root(right, left, len - left_len - 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...