Submission #1210890

#TimeUsernameProblemLanguageResultExecution timeMemory
1210890garam1732통행료 (IOI18_highway)C++20
0 / 100
9 ms4180 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<pi> adj[MAXN]; vector<vector<int> > adj1, adj2; queue<int> q; vector<ll> d1, d2; void bfs(int s, vector<ll> &d) { d[s] = 0; q.push(s); while(q.size()) { int here = q.front(); q.pop(); for(auto [there,w] : adj[here]) { if(d[there] > d[here]+1) { d[there] = d[here]+1; q.push(there); } } } } void bfs(int s, int t, vector<ll> &dst, vector<int>& v) { q.push(s); while(q.size()) { int here = q.front(); q.pop(); v.push_back(here); for(auto [there,w] : adj[here]) { if(dst[there] == dst[here]+1) { if(dst[there] < d2[there]+d1[there]-dst[there]) { q.push(there); } } } } } bool chk[MAXN]; vector<int> v1, v2; 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(pi(V[i], i)); adj[V[i]].push_back(pi(U[i], i)); } vector<int> w(m); ll len = ask(w)/A; int lb = 0, ub = m, 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; lb = mid+1; } else { ub = mid; } } int e = lb; int x = U[e], y = V[e]; d1.resize(N, INF); d2.resize(N, INF); bfs(x, d1); bfs(y, d2); adj1.resize(N); adj2.resize(N); bfs(x, y, d1, v1); bfs(y, x, d2, v2); lb = 0, ub = (int)v1.size()-1, mid; while(lb < ub) { mid = lb+ub>>1; memset(chk, 0, sizeof chk); for(int i=0; i<=mid; i++) chk[v1[i]]=1; w.resize(m); 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; } int p = v1[lb]; lb = 0, ub = (int)v2.size()-1, mid; while(lb < ub) { mid = lb+ub>>1; memset(chk, 0, sizeof chk); for(int i=0; i<=mid; i++) chk[v2[i]]=1; w.resize(m); 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; } int q = v2[lb]; answer(p, q); }
#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...