Submission #259929

#	Time	Username	Problem	Language	Result	Execution time	Memory
259929		medk	Highway Tolls (IOI18_highway)	C++14	0 / 100	251 ms	262148 KiB

highway

#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 initdist,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)==initdist){
		while(l<r){
			int md=(l+r)/2;
			for(int i=l;i<=md;i++){
				color(adj[i].x,centroid);
			}
			if(ask(toask)==initdist) 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)==initdist) l=md+1;
		else r=md;
		uncolor();
	}
	color(adj[l].x,centroid);
	ll get=ask(toask);
	uncolor();
	ll dst=(get-initdist)/(b-a)+1LL;
	atdist(centroid,-1,dst);
	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)==initdist) 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)==initdist) 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;
	}
	initdist=ask(toask);
	dist=initdist/a;
	find_first(0);
	find_second();
	answer(fst,scd);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31