Submission #342895

#	Time	Username	Problem	Language	Result	Execution time	Memory
342895		cki86201	Highway Tolls (IOI18_highway)	C++17	51 / 100	414 ms	11552 KiB

highway

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

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

vector <int> EV;
vector <pii> E[100010];
int dv[2][100010], chk[100010];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = szz(U);
	rep(i, M) E[U[i]].pb({V[i], i}), E[V[i]].pb({U[i], i});
	EV.resize(M);
	ll dist = ask(EV);
	int low = 0, high = M - 1;
	while(low < high) {
		int mid = (low + high) >> 1;
		rep(i, M) EV[i] = (low <= i && i <= mid);
		if(ask(EV) != dist) high = mid;
		else low = mid + 1;
	}
	int P = U[low], Q = V[low], tl = low;
	rep(u, 2) {
		int st = (u ? Q : P);
		vector <int> q; q.pb(st);
		rep(i, N) dv[u][i] = -1;
		dv[u][st] = 0;
		rep(i, szz(q)) {
			int t = q[i];
			for(auto [e, _] : E[t]) if(dv[u][e] == -1) {
				dv[u][e] = dv[u][t] + 1;
				q.pb(e);
			}
		}
	}
	auto Find = [&](int P, vector <int> &C, int dis[]) {
		sort(all(C), [&](int x, int y) { return dis[x] < dis[y]; });
		int low = 0, high = szz(C) - 1;
		while(low < high) {
			int mid = (low + high) >> 1;
			rep(i, M) EV[i] = (i != tl && chk[U[i]] != chk[V[i]]);
			for(int i=mid+1;i<szz(C);i++) {
				int x = C[i];
				for(auto [e, id] : E[x]) {
					if(dis[e] + 1 == dis[x]) EV[id] = 1;
				}
			}
			if(ask(EV) != dist) low = mid + 1;
			else high = mid;
		}
		return C[low];
	};
	vector <int> R[2];
	rep(i, N) {
		if(dv[0][i] < dv[1][i]) R[0].pb(i), chk[i] = 0;
		else if(dv[0][i] > dv[1][i]) R[1].pb(i), chk[i] = 1;
		else chk[i] = 2;
	}
	answer(Find(P, R[0], dv[0]), Find(Q, R[1], dv[1]));
}

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