Submission #300729

#	Time	Username	Problem	Language	Result	Execution time	Memory
300729		TMJN	Highway Tolls (IOI18_highway)	C++17	5 / 100	178 ms	43640 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

struct edge{
	int to,id;
};

vector<edge>V[900000];
int dist[900000];

void dfs(int x,int from){
	for(edge e:V[x]){
		if(e.to==from)continue;
		dist[e.to]=dist[x]+1;
		dfs(e.to,x);
	}
}

void find_pair(int N,vector<int>u,vector<int>v,int A,int B){
	for(int i=0;i<N;i++){
		V[i].clear();
	}
	int M=u.size();
	assert(M==N-1);
	for(int i=0;i<M;i++){
		V[u[i]].push_back({v[i],i});
		V[v[i]].push_back({u[i],i});
	}
	long long Base=ask(vector<int>(M,0));
	int path_len=Base/A;
	int l,r;
	l=-1;
	r=M-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			K[i]=1;
		}
		int t=ask(K);
		if(t>Base){
			r=m;
		}
		else{
			l=m;
		}
	}
	int p=u[r];
	int q=v[r];
	vector<int>K(M,0);
	K[r]=1;
	queue<int>que;
	que.push(q);
	while(!que.empty()){
		int x=que.front();
		que.pop();
		for(edge e:V[x]){
			if(K[e.id])continue;
			K[e.id]=true;
			que.push(e.to);
		}
	}
	K[r]=0;
	long long t=ask(K);
	int len=(t-Base)/(B-A);
	int S,T;
	for(int i=0;i<N;i++){
		dist[i]=-1;
	}
	dist[q]=0;
	dfs(q,p);
	vector<int>W;
	for(int i=0;i<N;i++){
		if(dist[i]==len){
			W.push_back(i);
		}
	}
	l=-1;
	r=W.size()-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			for(edge e:V[W[i]]){
				K[e.id]=1;
			}
		}
		if(Base!=ask(K)){
			r=m;
		}
		else{
			l=m;
		}
	}
	S=W[r];
	W.clear();
	for(int i=0;i<N;i++){
		dist[i]=-1;
	}
	dist[p]=0;
	dfs(p,q);
	for(int i=0;i<N;i++){
		if(dist[i]==path_len-1-len){
			W.push_back(i);
		}
	}
	l=-1;
	r=W.size()-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			for(edge e:V[W[i]]){
				K[e.id]=1;
			}
		}
		if(Base!=ask(K)){
			r=m;
		}
		else{
			l=m;
		}
	}
	T=W[r];
	answer(S,T);
}

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