Submission #1135651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135651		alterio	Highway Tolls (IOI18_highway)	C++20	51 / 100	558 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 9e4 + 100;

int N, M;
bool processed[mxn], mark[mxn];
int id[mxn], dep[mxn], sz[mxn];
vector<pair<int, int>> g[mxn];
vector<int> w;

int getSize(int cur, int P = -1) {
	sz[cur] = !processed[cur];
	for (auto to : g[cur]) {
		if (to.first == P) continue;
		dep[to.first] = dep[cur] + 1;
		id[to.first] = to.second;
		sz[cur] += getSize(to.first, cur);
	}
	return sz[cur];
}

void Erase(bool found) {
	for (int i = 0; i < N; i++) {
		if (mark[i] != found) processed[i] = 1;
	}
}

void Set(int cur) {
	if (!sz[cur]) return;
	if (!processed[cur]) {
		mark[cur] = 1;
		w[id[cur]] = 1;
	}
	for (auto to : g[cur]) {
		if (dep[to.first] < dep[cur]) continue;
		Set(to.first);
	}
}

void Fill(int cur, int x) {
	for (auto to : g[cur]) {
		if (dep[to.first] < dep[cur] || !x) continue;
		if (sz[to.first] > x) {
			Fill(to.first, x);
			return;
		}
		x -= sz[to.first];
		Set(to.first);
	}
}

int Find(int fixed = 0) {
	memset(processed, 0, sizeof(processed));
	processed[fixed] = 1;
	w.resize(M, 0);
	for (int i = 0; i < M; i++) w[i] = 0;
    int sz = N - 1;
	long long sum = ask(w);
	int times = log2(sz) + 2;
	for (int i = 0; i < times; i++) {
		memset(dep, 0, sizeof(dep));
		memset(mark, 0, sizeof(mark));
		getSize(fixed);
		for (int j = 0; j < M; j++) w[j] = 0;
		int amm = sz / 2;
		if (amm == 0) break;
		Fill(fixed, amm);
		long long newSum = ask(w);
		Erase(newSum != sum);
		sz -= amm;
	}
	int ind;
	for (int i = 0; i < N; i++) if (!processed[i]) ind = i;
	return ind;
}

void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
    N = _N;
	M = U.size();
	for (int i = 0; i < M; i++) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	int S = Find(0);
	int T = Find(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