Submission #348609

#	Time	Username	Problem	Language	Result	Execution time	Memory
348609		amunduzbaev	Highway Tolls (IOI18_highway)	C++14	5 / 100	140 ms	7788 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];
vector<int> tr;
int ans;

int dfs(int u, int p){
	//if(sz(edges[u]) == 1) return u;
	
	vv<pii> tt;
	for(auto x:edges[u]) if(x.ff != p) tt.pb(x);
	
	int l = 0, r = sz(tt)-1;
	
	for(int i=0;i<sz(tt);i++) tr[tt[i].ss] = 1;
	int res = ask(tr);
	if(res == ans) return u;
	for(int i=0;i<sz(tt);i++) tr[tt[i].ss] = 0;
	
	while(l+1 < r){
		int m = (l + r)>>1;
		for(int i=m;i<sz(tt);i++) tr[tt[i].ss] = 1;
		int res = ask(tr);
		if(res == ans){
			for(int i=m;i<sz(tt);i++) tr[tt[i].ss] = 0;
			r = m-1;
		}else{
			for(int i=m;i<sz(tt);i++) tr[tt[i].ss] = 0;
			l = m;
		}
	}
	
	int m = r;
	for(int i=m;i<sz(tt);i++) tr[tt[i].ss] = 1;
	res = ask(tr);
	if(res != ans){
		for(int i=m;i<sz(tt);i++) tr[tt[i].ss] = 0;
		l = m;
	}
	
	return dfs(tt[l].ff, u);
}

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);
	ans = ask(tr);
	
	answer(0, dfs(0, -1));
}

/*

7 6 1 2 0 5
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