| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 259926 | medk | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()
using namespace std;
vector<vector<pair<int,int>>> g;
vector<bool> blocked;
vector<int> sz, toask, edges;
vector<pair<int,int>> cand;
int n,m;
ll norm,a,b,dist;
int fst,scd;
void calc_sz(int u, int par=-1){
sz[u]=1;
for(auto p:g[u]){
if(p.x==par || blocked[p.x]) continue;
calc_sz(p.x,u);
sz[u]+=sz[p.x];
}
}
int find_centroid(int u, int par, int comp){
for(auto p:g[u]){
if(p.x==par || blocked[p.x]) continue;
if(sz[p.x]>=comp/2) return find_centroid(p.x,u,comp);
}
return u;
}
void color(int u, int par){
for(auto p:g[u]){
if(p.x==par || blocked[p.x]) continue;
toask[p.y]=1;
edges.pb(p.y);
color(p.x,u);
}
}
void uncolor(){
for(int e:edges) toask[e]=0;
edges.clear();
}
void atdist(int u, int par, int goald, int d=0){
for(auto p:g[u]){
if(p.x==par || blocked[p.x]) continue;
if(d==goald-1){
cand.pb(p);
}
else atdist(p.x,u,goald,d+1);
}
}
void find_first(int u){
calc_sz(u);
int centroid=find_centroid(u,u,sz[u]);
vector<pair<int,int>> adj;
for(auto p:g[centroid]){
if(blocked[p.x]) continue;
adj.pb(p);
edges.pb(p.y);
toask[p.y]=1;
}
uncolor();
int l=0, r=sz(adj)-1;
if(ask(toask)==norm){
while(l<r){
int md=(l+r)/2;
for(int i=l;i<=md;i++){
color(adj[i].x);
}
if(ask(toask)==norm) l=md+1;
else r=md;
uncolor();
}
blocked[centroid]=1;
find_first(adj[l].x);
return;
}
while(l<r){
int md=(l+r)/2;
for(int i=l;i<=md;i++){
toask[adj[i].y]=1;
edges.pb(adj[i].y);
}
if(ask(toask)==norm) l=md+1;
else r=md;
uncolor();
}
color(adj[i].x);
ll get=ask(toask);
uncolor();
ll dst=(get-norm)/(b-a)+1LL;
atdist(centroid,-1,dst);
int l=0, r=sz(cand);
while(l<r){
int md=(l+r)/2;
for(int i=l;i<=md;i++){
toask[cand[i].y]=1;
edges.pb(cand[i].y);
}
if(ask(toask)==norm) l=md+1;
else r=md;
uncolor();
}
fst=cand[l].x;
}
void find_second(){
for(int i=0;i<n;i++) blocked[i]=0;
cand.clear();
atdist(fst,-1,dist);
int l=0, r=sz(cand);
while(l<r){
int md=(l+r)/2;
for(int i=l;i<=md;i++){
toask[cand[i].y]=1;
edges.pb(cand[i].y);
}
if(ask(toask)==norm) l=md+1;
else r=md;
uncolor();
}
scd=cand[l].x;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
n=N, m=sz(U), a=A, b=B;
g.resize(n), blocked.resize(n), sz.resize(n), toask.resize(m);
for(int i=0;i<m;i++){
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
toask[i]=0;
}
norm=ask(toask);
dist=norm/a;
find_first(0);
find_second();
answer(fst,scd);
}