Submission #138133

#TimeUsernameProblemLanguageResultExecution timeMemory
138133RockyBHighway Tolls (IOI18_highway)C++17
51 / 100
353 ms19764 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; bool was[MAX_N]; void bfs(int v = 0, int p = -1, int lvl = 0) { dep[v] = 0; was[v] = 1; queue <int> q; q.push(v); while (sz(q)) { int x = q.front(); q.pop(); for (auto to : g[x]) { if (!was[to.f]) { dep[to.f] = dep[x] + 1; was[to.f] = 1; q.push(to.f); if (dep[x] + 1 == depth) { // e.pb(to.s); } } } } /// ------------------------- /*return; 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]); } // if (0) 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; } bfs(S); rep(i, 0, n) { for (auto to : g[i]) { if (min(dep[i], dep[to.f]) + 1 == depth) { e.pb(to.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]; bool was[MAX_N]; void bfs(int v = 0, int p = -1, int lvl = 0) { dep[v] = 0; was[v] = 1; queue <int> q; q.push(v); while (sz(q)) { int x = q.front(); q.pop(); for (auto to : g[x]) { if (!was[to.f]) { dep[to.f] = dep[x] + 1; was[to.f] = 1; q.push(to.f); } } } // ------------------------ /*return; 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]); } // if (0) 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 bfs(); rep(i, 0, n) { for (auto to : g[i]) { edges[min(dep[i], dep[to.f])].pb(to.s); } } 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; } if (res == -1) { if (0) cerr << "DIDN't FIND DEPTH of S" << endl; } 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 if (0) cerr << "DIDN'T FIND S" << endl; 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 int S = FindS :: GetS(); if (0) cerr << S << endl; Tree :: solve(S); return; answer(0, N - 1); }

Compilation message (stderr)

highway.cpp: In function 'int FindS::GetS()':
highway.cpp:192: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...