Submission #775556

#	Time	Username	Problem	Language	Result	Execution time	Memory
775556		Baytoro	Highway Tolls (IOI18_highway)	C++17	5 / 100	116 ms	44344 KiB

highway

#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+5;
#define sc second
#define fr first
#define pb push_back
vector<pair<int,int>> g[NN];
vector<int> edge(NN),vertex(NN);
int cnt=0;

void dfs(int x, int p){
	for(auto it: g[x]){
		if(it.sc==p) continue;
		vertex[cnt]=it.sc;
		edge[it.fr]=cnt++;
		dfs(it.sc,x);
	}
}
int m;
int dist;
vector<int> w;
int get_first(){
	int l=0,r=m-1;
	while(l!=r){
		int md=(l+r)/2;
		for(int i=0;i<m;i++)
			w[i]=(i<=md);
		if(ask(w)!=dist)
			r=md;
		else
			l=md+1;
	}
	return l;
}
int get_last(){
	int l=-1,r=cnt-1;
	while(l!=r){
		int md=(l+r+1)/2;
		for(int i=0;i<m;i++){
			w[i]=(edge[i]>=md);
		}
		if(dist!=ask(w))
			l=md;
		else
			r=md-1;
	}
	return l;
}
int ans[2];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	m=u.size();
	w.resize(m);
	dist=ask(w);
	
	for(int i=0;i<m;i++){
		g[u[i]].pb({i,v[i]});
		g[v[i]].pb({i,u[i]});
	}
	
	//dfs(0,-1);
	
	int e=get_first();
	int A=u[e],B=v[e];
	for(int i=0;i<2;i++){
		cnt=0;
		edge.assign(m,-1);
		dfs(A,B);
		
		int k=get_last();
		ans[i]= k==-1?A:vertex[k];
		swap(A,B);
	}
	answer(ans[0],ans[1]);
}

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