Submission #348927

#	Time	Username	Problem	Language	Result	Execution time	Memory
348927		amunduzbaev	Highway Tolls (IOI18_highway)	C++14	5 / 100	316 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

#define pb push_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define vv vector 
typedef pair<int, int> pii; 

const int NN = 1e5+5;
vv<pii> edges[NN];
vv<int> tr, tt;
int un[NN], used[NN], wh[NN], dis, rr, dd[NN];

void dfs(int u, int p, int d = 0){
	if(d == dis){
		tt.pb(u);
	}
	dd[u] = d;
	for(auto x:edges[u]){
		if(x.ff == p) continue;
		dfs(x.ff, u, d+1);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for(int i=0;i<sz(V);i++){
		edges[V[i]].pb({U[i], i});
		edges[U[i]].pb({V[i], i});
	}
	
	tr.resize(sz(V), 0);
	int ans = ask(tr);
	dis = ans/A;
	
	/*
	queue<int> qq;
	qq.push(0);
	un[0] = 1, used[0] = 1;
	int last = 2;
	
	while(!qq.empty()){
		int cur = qq.front(); qq.pop();
		for(auto x:edges[cur]){
			if(used[x.ff]) continue;
			un[x.ff] = last++;
			used[x.ff] = 1;
			wh[last] = x.ff;
			qq.push(x.ff);
		}
	}
	
	
	int l = 0, r = last-1;
	int br = dis * B;
	
	while(l < r){
		int m = (l + r)>>1;
		for(int i=l;i<=m;i++){
			for(auto x:edges[i]){
				if(x.ff > m || x.ff < i) continue;
				tr[x.ss] = 1;
			}
		}
		int res = ask(tr);
		
		for(int i=l;i<=m;i++){
			for(auto x:edges[i]){
				if(x.ff > m || x.ff < i) continue;
				tr[x.ss] = 0;
			}
		}
		
		if(res == br) r = m;
		else l = m+1;
	}
	*/
	//tt.clear();
	
	rr = 0;
	dfs(rr, -1, 0);
	//cout<<dis<<"\n";
	//for(int i=0;i<N;i++) cout<<dd[i]<<" ";
	//cout<<"\n";
	
	int l = 0, r = sz(tt)-1;
	//for(auto x:tt) cout<<x<<" ";
	//cout<<endl;
	while(l < r){
		int m = (l + r)>>1;
		//cout<<l<<" "<<r<<endl;
		for(int i=l;i<=m;i++){
			for(auto x:edges[tt[i]]){
				if(dd[x.ff] < dd[tt[i]]) tr[x.ss] = 1;
				//cout<<x.ff<<" "<<dd[x.ff]<<endl;
			}
		}
		
		int res = ask(tr);
		
		//for(auto x:tr)cout<<x<<" ";
		//cout<<"\n";
		
		//cout<<res<<"\n";
		for(int i=l;i<=m;i++){
			for(auto x:edges[tt[i]])
				if(dd[x.ff] < dd[tt[i]]) tr[x.ss] = 0;
		}
		
		if(res > dis*A) r = m;
		else l = m+1;	
	}
	
	//cout<<"\n"<<rr<<" "<<tt[l]<<"\n";
	answer(rr, tt[l]);
}

/*

7 6 1 2 0 1
0 1
0 4
1 2
1 3
4 5
4 6

*/

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