Submission #97164

#	Time	Username	Problem	Language	Result	Execution time	Memory
97164		youngyojun	Highway Tolls (IOI18_highway)	C++11	100 / 100	487 ms	26320 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef long long ll;

const int MAXN = 90055;
const int MAXM = 130055;

vector<int> G[MAXN], BEV;

vector<int> PEV[2][MAXN], O[2];
int C[2][MAXN], D[2][MAXN];
int A[MAXM], B[MAXM];

int ud[MAXN];

int N, M, CA, CB, L, W, AS, AT;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

void getW() {
	int s = 0, e = M-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V(M, 0);
		fill(V.begin(), V.begin()+m+1, 1);
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	W = s;
}

void calC() {
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	for(int t : {0, 1}) {
		queue<int> PQ;
		C[t][(t ? B : A)[W]] = 1;
		PQ.push((t ? B : A)[W]);
		for(int i, d; !PQ.empty(); PQ.pop()) {
			i = PQ.front();
			d = C[t][i] + 1;
			for(int e : G[i]) {
				int v = A[e] + B[e] - i;
				if(C[t][v]) continue;
				C[t][v] = d;
				PQ.push(v);
			}
		}
	}
}

void dfs(int D[], vector<int> PEV[], int i) {
	for(int e : G[i]) {
		int v = A[e] + B[e] - i;
		PEV[v].eb(e);
		if(D[v]) continue;
		D[v] = D[i] + 1;
		dfs(D, PEV, v);
	}
}

void findS() {
	int s = 0, e = sz(O[0])-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V = BEV;
		for(int i = 0; i <= m; i++)
			V[PEV[0][O[0][i]][0]] = 1;
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	AS = O[0][s];
}

void findT() {
	vector<int> HV;
	int dep = L-D[0][AS]+1;
	for(int i = 0; i < N; i++) if(dep == D[1][i]) HV.eb(i);
	int s = 0, e = sz(HV)-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V = BEV;
		for(int i = 0; i <= m; i++)
			V[PEV[1][HV[i]][0]] = 1;
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	AT = HV[s];
}

void solve() {
	L = ask(vector<int>(M, 0)) / CA;
	getW();
	calC();
	for(int i = 0; i < N; i++) G[i].clear();
	for(int i = 0, a, b; i < M; i++) {
		a = A[i]; b = B[i];
		if(C[0][a] == C[0][b] || C[1][a] == C[1][b]
			|| C[0][a] == C[1][a] || C[0][b] == C[1][b]
			|| (C[0][a] < C[0][b]) != (C[1][a] < C[1][b])) {
			BEV.eb(1);
			continue;
		}
		BEV.eb(0);
		if(C[0][a] < C[0][b]) G[a].eb(i);
		else G[b].eb(i);
	}
	BEV[W] = 0;
	for(int t : {0, 1}) {
		int v = (t ? B : A)[W];
		D[t][v] = 1; PEV[t][v].eb(W);
		dfs(D[t], PEV[t], v);
		for(int i = 0; i < N; i++)
			if(D[t][i]) O[t].eb(i);
		sort(allv(O[t]), [&](int a, int b) {
			return D[t][a] > D[t][b];
		});
		iota(ud, ud+N, 0);
		for(int v : O[t]) {
			auto &V = PEV[t][v];
			int pe = -1;
			for(int e : V) {
				int p = A[e] + B[e] - v;
				if(uf(p) == uf(v)) continue;
				uf(p, v);
				pe = e;
				break;
			}
			for(int e : V) if(e != pe) BEV[e] = 1;
			V.clear(); V.eb(pe);
		}
	}
	findS();
	findT();
	answer(AS, AT);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::N = N; ::M = U.size(); ::CA = A; ::CB = B;
	for(int i = 0; i < ::M; i++) {
		::A[i] = U[i];
		::B[i] = V[i];
	}
	solve();
}

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