Submission #1199079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199079		Gr1sen	Highway Tolls (IOI18_highway)	C++20	0 / 100	235 ms	327680 KiB

highway

#include "highway.h"
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<random>

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>
#define vvp vector<vp>

vvp Adj;
vi CZ;
vi P;
vi w;
int root;
int s, t, m;
ll disa;
mt19937 mt(12309142);

void print(vi &L) {
	cerr << "{";
	for (auto i : L) cerr << i << ", ";
	cerr << "}" << endl;
}

void print(vp &L) {
	cerr << "{";
	for (auto i : L) cerr << "{" << i.first << ", " << i.second << "}, ";
	cerr << "}\n";
}

int dfs(int p, int dfp) {
	P[p] = dfp;
	int a = 1;
	for (auto [i, _] : Adj[p]) {
		if (i == dfp) continue;
		a += dfs(i, p);
	}
	return CZ[p] = a;
}

int oink(int p, int l, int r, int sz) {
	//cerr << "oink(" << p << ", " << l << ", " << r << ", " << sz << ")" << endl;
	//cerr << "Adj[p] : ";
	if (Adj[p][r-1].first == P[p]) r--;
	if (Adj[p][l].first == P[p]) l++;
	//print(Adj[p]); 
	if (l == r) return p;
	if (l+1 == r) {
		int c = Adj[p][l].first;
		w = vi(m, 0);
		w[Adj[p][l].second] = 1;
		ll res = ask(w);
		//cerr << "res : " << res << endl;
		if (res == disa) return p;
		return oink(c, 0, Adj[c].size(), CZ[c]);
	}
	w = vi(m, 0);
	int k = 0;
	int i = l;
	for (; i < r-1; i++) {
		if (Adj[p][i].first == P[p]) continue;
		if ((sz-1)/2 < k) break;
		k += CZ[Adj[p][i].first];
		w[Adj[p][i].second] = 1;
	}
	//cerr << "l : " << l << ", i : " << i << endl;
	ll res = ask(w);
	//cerr << "res : " << res << endl;
	if (res == disa) return oink(p, i, r, sz-k);
	return oink(p, l, i, k);
}

void find_pair(int n, vi U, vi V, int A, int B) {
	m = U.size();
	Adj = vvp(n);
	CZ = vi(n);
	P = vi(n);
	//root = mt()%n;
	root = 0;
	for (int i = 0; i < m; i++) {
		Adj[V[i]].push_back({U[i], i});
		Adj[U[i]].push_back({V[i], i});
	}
	for (int i = 0; i < n; i++) {
		shuffle(Adj[i].begin(), Adj[i].end(), mt);
	}
	dfs(root, -1);
	s = 0; t = -1;
	w = vi(m, 0);
	disa = ask(w);
	//cerr << "disa : " << disa << endl;
	t = oink(root, 0, Adj[root].size(), CZ[root]);
	//cerr << s << " " << t << endl;
	answer(s, t);
}

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