Submission #765795

#	Time	Username	Problem	Language	Result	Execution time	Memory
765795		ono_de206	Highway Tolls (IOI18_highway)	C++14	18 / 100	133 ms	30412 KiB

highway

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 1e5 + 10;
int id[mxn], par[mxn], sz;
vector<int> ver[mxn];
vector<pair<int, int>> g[mxn];

void dfs(int to, int fr, int now) {
	sz = max(sz, now);
	ver[now].pb(to);
	par[to] = fr;
	for(auto it : g[to]) {
		if(it.ff == fr) continue;
		id[it.ff] = it.ss;
		dfs(it.ff, to, now + 1);
	}
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
	int m = u.size();
	for(int i = 0; i < m; i++) {
		g[u[i]].eb(v[i], i);
		g[v[i]].eb(u[i], i);
	}
	vector<int> q(m, 1);
	dfs(0, -1, 0);
	long long tot = ask(q);
	int dis = tot / B;
	int L = 0, R = sz + 1;
	while(R - L > 1) {
		int M = (L + R) / 2;
		for(int i = 0; i < m; i++) q[i] = 1;
		for(int i = 1; i <= M; i++) {
			for(int x : ver[i]) {
				q[id[x]] = 0;
			}
		}
		long long ans = ask(q);
		if(ans == tot) L = M;
		else R = M;
	}
	int D = L;
	L = -1, R = sz;
	while(R - L > 1) {
		int M = (L + R) / 2;
		for(int i = 0; i < m; i++) q[i] = 1;
		for(int i = sz; i > M; i--) {
			for(int x : ver[i]) {
				q[id[x]] = 0;
			}
		}
		long long ans = ask(q);
		if(ans == tot) R = M;
		else L = M;
	}
	int U = R;
	int ans1 = -1, ans2 = -1;
	L = 0, R = (int)ver[U].size() - 1;
	while(L < R) {
		int M = (L + R) / 2;
		for(int i = 0; i < m; i++) q[i] = 1;
		for(int i = L; i <= M; i++) {
			q[id[ver[U][i]]] = 0;
		}
		long long ans = ask(q);
		if(ans == tot) L = M + 1;
		else R = M;
	}
	ans1 = ver[U][L];
	if(U - D == dis) {
		ans2 = ans1;
		for(int i = 0; i < dis; i++) {
			ans2 = par[ans2];
		}
	} else {
		int MID = D + dis - (U - D);
		L = 0, R = (int)ver[MID].size() - 1;
		while(L < R) {
			int M = (L + R) / 2;
			for(int i = 0; i < m; i++) q[i] = 1;
			for(int i = L; i <= M; i++) {
				q[id[ver[MID][i]]] = 0;
			}
			if(MID == U) q[id[ans1]] = 1;
			long long ans = ask(q);
			if(ans == tot) L = M + 1;
			else R = M;
		}
		ans2 = ver[MID][L];
	}
	assert(ans1 != ans2);
	answer(ans1, ans2);
	// answer(0, 1);
}

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