Submission #1211035

#TimeUsernameProblemLanguageResultExecution timeMemory
1211035garam1732Highway Tolls (IOI18_highway)C++20
In queue
0 ms0 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define bl ' ' #define endl '\n' #define all(v) (v).begin(), (v).end() #define comp(v) (v).erase(unique(all(v)), (v).end()) #define lbd(v,x) lower_bound(all(v), (x))-(v).begin() #define ubd(v,x) upper_bound(all(v), (x))-(v).begin() typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, int> pii; typedef pair<int, pi> ipi; typedef pair<pi, pi> pipi; typedef pair<ll, ll> pll; const int MAXN = 100100*1; const ll MOD = 998244353; const ll INF = 1e16; vector<int> adj[MAXN]; bool chk[MAXN]; queue<pi> q; vector<ll> d; vector<int> v[2]; void bfs(int s, int t) { d[s] = d[t] = 0; q.push(pi(s, 0)); q.push(pi(t, 1)); while(q.size()) { int here = q.front().ff; int col = q.front().ss; q.pop(); v[col].push_back(here); for(int there : adj[here]) { if(d[there] > d[here]+1) { d[there] = d[here]+1; q.push(pi(there, col)); } } } } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { int m = U.size(); for(int i=0; i<m; i++) { adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } vector<int> w(m); ll len = ask(w)/A; int lb = 0, ub = m-1, mid; while(lb < ub) { mid = lb+ub>>1; for(int i=lb; i<=mid; i++) w[i]=1; ll res = ask(w); if(res > A*len) { for(int i=lb; i<=mid; i++) w[i]=0; ub = mid; } else { lb = mid+1; } } int e = lb; int x = U[e], y = V[e]; d.resize(N, INF); bfs(x, y); int ans[2]; for(int t : {0,1}) { lb = 0, ub = (int)v[t].size()-1, mid; while(lb < ub) { mid = lb+ub>>1; w.clear(); w.resize(m); memset(chk, 0, sizeof chk); for(int i=mid+1; i<v[t].size(); i++) chk[v[t][i]] = 1; for(int i=0; i<m; i++) { if(chk[U[i]] != chk[V[i]]) w[i] = 1; } ll res = ask(w); if(res == A*len) ub = mid; else lb = mid+1; } ans[t] = v[t][lb]; } answer(ans[0], ans[1]); }