Submission #138118

#TimeUsernameProblemLanguageResultExecution timeMemory
138118RockyBHighway Tolls (IOI18_highway)C++17
51 / 100
265 ms32936 KiB
// In The Name Of God #include <bits/stdc++.h> #include "highway.h" using namespace std; #define f first #define s second #define pb push_back #define pp pop_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, l, r) for (int i = (l); i >= (r); i--) #define nl '\n' #define ioi exit(0); typedef long long ll; const int MAX_N = (int)1e5 + 7; const int INF = (int)1e9 + 7; int n, m, A, B; vector < pair <int, int > > g[MAX_N]; namespace Tree { // We suppose that S or T is 0 int depth; ll min_len; int dep[MAX_N]; vector <int> e; void dfs(int v = 0, int p = -1, int lvl = 0) { dep[v] = lvl; for (auto to : g[v]) { if (to.f != p) { dfs(to.f, v, lvl + 1); if (lvl + 1 == depth) { e.pb(to.s); } } } } int id(const vector <int> &x) { if (sz(x) == 1) return x[0]; int mid = sz(x) / 2; vector <int> q(m, 0), sol; rep(i, 0, mid - 1) { q[x[i]] = 1; sol.pb(x[i]); } // cerr << sz(x) << endl; assert(sz(sol)); ll cur = ask(q); if (cur > min_len) return id(sol); vector <int> on; rep(i, mid, sz(x) - 1) on.pb(x[i]); return id(on); } void solve(int S = 0) { if (n != m + 1) return; { vector <int> q(m, 0); min_len = ask(q); depth = min_len / A; } dfs(S); int ed = id(e); rep(i, 0, n - 1) { for (auto it : g[i]) { if (it.s == ed) { if (dep[i] > dep[it.f]) answer(S, i); else answer(S, it.f); return; } } } assert(0); } } namespace FindS { int dist; int dep[MAX_N]; vector <int> edges[MAX_N]; void dfs(int v = 0, int p = -1, int lvl = 0) { dep[v] = lvl; for (auto to : g[v]) { if (to.f != p) { dfs(to.f, v, lvl + 1); edges[lvl].pb(to.s); } } } int id(const vector <int> &x) { if (sz(x) == 1) return x[0]; int mid = sz(x) / 2; vector <int> q(m, 0), sol; rep(i, 0, mid - 1) { q[x[i]] = 1; sol.pb(x[i]); } // cerr << sz(x) << endl; assert(sz(sol)); ll cur = ask(q); if (cur > (ll)dist * A) return id(sol); vector <int> on; rep(i, mid, sz(x) - 1) on.pb(x[i]); return id(on); } int GetS() { { vector <int> q(m, 0); dist = ask(q) / A; } // dist of path dfs(); int l = 0, r = n, res = -1; while (l <= r) { int mid = l + r >> 1; vector <int> q(m, 0); rep(i, 0, mid) for (auto ind : edges[i]) q[ind] = 1; ll cur = ask(q); if (cur == (ll)dist * B) res = mid, r = mid - 1; else l = mid + 1; } assert(res != -1); // found depth of S { int ind = id(edges[res]); rep(i, 0, n - 1) { for (auto to : g[i]) { if (to.s == ind) { if (dep[i] > dep[to.f]) return i; return to.f; } } } } // found S assert(0); } } void find_pair(int N, vector<int> U, vector<int> V, int _A, int _B) { n = N; m = sz(U); A = _A; B = _B; rep(i, 0, m - 1) { g[V[i]].pb({U[i], i}); g[U[i]].pb({V[i], i}); } // copy finished Tree :: solve(FindS :: GetS()); return; answer(0, N - 1); }

Compilation message (stderr)

highway.cpp: In function 'int FindS::GetS()':
highway.cpp:139:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 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...