Submission #297188

#	Time	Username	Problem	Language	Result	Execution time	Memory
297188		Saboon	Highway Tolls (IOI18_highway)	C++17	51 / 100	840 ms	10916 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 90000 + 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];

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	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);
	memset(h, -1, sizeof h);
	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;
				par[u] = v;
			}
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	sort(p, p+n, [](int A, int B){
		return h[A] > h[B];
	});
	int S = -1, T = -1;
	for (int _ = 0; _ < 2; _++){
		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];
				if (mark[v])
					continue;
				for (auto [u,idx] : g[v]){
					if (!mark[u]){
						Q[idx] |= 1;
//						cerr << "Edge " << v << " " << u << endl;
					}
				}
			}
			ll nowCost = ask(Q);
			for (int i = 0; i <= mid; i++){
				int v = p[i];
				if (mark[v])
					continue;
				for (auto [u,idx] : g[v])
					Q[idx] &= 0;
			}
//			cerr << _ << " : " << L << " " << mid << " " << R << " -> " << nowCost << " ! " << Cost << endl;
			if (nowCost == Cost)
				L = mid;
			else
				R = mid;
		}
		if (_ == 0){
			S = p[R];
			int x = S;
			while (h[x] > 0){
				mark[x] = 1;
				x = par[x];
			}
		}
		else
			T = p[R];
	}
//	cerr << S << " " << T << endl;
	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