Submission #297219

#	Time	Username	Problem	Language	Result	Execution time	Memory
297219		Saboon	Highway Tolls (IOI18_highway)	C++17	51 / 100	884 ms	13636 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector<int> Q;
ll Cost = 0;
int p[maxn], par[maxn];
vector<pair<int,int>> g[maxn];
bool mark[maxn];

int get(int L, int R){
	if (L+1 == R)
		return L;
	int mid = (L + R) >> 1;
	for (int v = L; v < mid; v++)
		for (auto [u,idx] : g[v])
			Q[idx] |= 1;
	ll nowCost = ask(Q);
	for (int v = L; v < mid; v++)
		for (auto [u,idx] : g[v])
			Q[idx] &= 0;
	if (nowCost != Cost)
		return get(L,mid);
	else
		return get(mid,R);
}

int Que[maxn], head = 0, tail = 0, h[maxn];
int n;

int Get(int v){
	memset(h, -1, sizeof h);
	tail = head = 0;
	h[v] = 0, Que[head++] = v;
	while (tail < head){
		int v = Que[tail++];
		for (auto [u,idx] : g[v])
			if (h[u] == -1)
				h[u] = h[v]+1, Que[head++] = u;
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	sort(p, p+n, [](int A, int B){
		return h[A] > h[B];
	});
	int L = -1, R = n-1;
	while (R-L > 1){
		int mid = (L+R) >> 1;
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] |= 1;
		}
		ll nowCost = ask(Q);
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] &= 0;
		}
		if (nowCost == Cost)
			L = mid;
		else
			R = mid;
	}
	return p[R];
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	::n = n;
	int m = U.size();
	Q.resize(m);
	for (int i = 0; i < m; i++){
		Q[i] = 0;
		g[V[i]].push_back({U[i],i});
		g[U[i]].push_back({V[i],i});
	}
	Cost = ask(Q);
	int v = get(0, n);
	int S = Get(v);
	int T = Get(S);
	answer(S,T);
}

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