Submission #349395

#	Time	Username	Problem	Language	Result	Execution time	Memory
349395		amunduzbaev	Highway Tolls (IOI18_highway)	C++14	51 / 100	294 ms	21544 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; 
#define ll long long
 
const int NN = 130005;
vv<pii> edges[NN];
vv<pii> gg[NN];
vv<int> tr;
vv<int> tt;
int un[NN], used[NN], wh[NN], rr, dd[NN], on[NN], l, r;
ll dis; 
 
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;
		on[x.ff] = x.ss;
		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++){
		gg[V[i]].pb({U[i], i});
		gg[U[i]].pb({V[i], i});
	}
	
	int mm = sz(V);
	tr.resize(mm, 0);
	dis = ask(tr)/A;
	
	l = 0, r = mm-1;
	while(l < r){
		int m = (l + r-1)>>1;
		for(int i=l;i<=m;i++) tr[l] = 1;
		
		ll res = ask(tr);
		tr.assign(mm, 0);
		if(res > dis*A) r = m;
		else l = m+1;
	}
	
	rr = V[l];
	queue<int> q;
	q.push(rr);
	used[rr] = 1;
	vector<int> tmp(mm, 1); 
	
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(auto x : gg[cur]){
			if(used[x.ff]) continue;
			edges[cur].pb(x);
			edges[x.ff].pb({cur, x.ss});
			tmp[x.ss] = 0;
			used[x.ff] = 1;
			q.push(x.ff);
		}
	}
	queue<int> qq;
	qq.push(0);
	memset(used, 0, sizeof used);
	un[0] = 1, used[0] = 1;
	int last = 1;
	wh[last] = 0;
	
	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);
		}
	}
	
	l = 1, r = last;
	ll br = dis * B;
	while(l < r){
		int m = (l + r -1)>>1;
		tr = tmp;
		
		for(int i=1;i<=m;i++){
			for(auto x:edges[wh[i]]){
				if(un[x.ff] > m) continue;
				tr[x.ss] = 1;
			}
		}
		
		ll res = ask(tr);
		
		if(res < br) l = m+1;
		else r = m;
	}
	
	rr = wh[l];
	dfs(rr, -1, 0);
	
	l = 0, r = sz(tt)-1;
	
	while(l < r){
		int m = (l + r)>>1;
		tr = tmp;
		for(int i=0;i<=m;i++) tr[on[tt[i]]] = 1;
		ll res = ask(tr);
		
		if(res > dis*A) r = m;
		else l = m+1;
	}
	
	answer(rr, tt[l]);
}
 
/*
 
7 6 1 2 0 4
0 1 
0 2 
0 3 
3 4 
2 6 
3 5 
 
*/
 
 

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