Submission #404281

#	Time	Username	Problem	Language	Result	Execution time	Memory
404281		SeDunion	Highway Tolls (IOI18_highway)	C++17	51 / 100	308 ms	14148 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;

int M, N;
ll Ask(vector<int>Q) {
	vector<int>W(M);
	for (int i : Q) W[i] = 1;
	ll res = ask(W);
	for (int i : W) cerr << i << " ";
	cerr << ": W " << res << endl;;
	return res;
}
ll Ask(vector<int>Q, vector<int>P) {
	for (int i : P) Q.emplace_back(i);
	return Ask(Q);
}

const int MAXN = 1e5;
vector<int> order, was, d, U, V;
vector<pair<int,int>>g[MAXN];

void bfs(int root) {
	d.assign(N, -1);
	queue<int>q;
	q.push(root);
	d[root] = 0;
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto [to, id] : g[v]) if (d[to] == -1) {
			d[to] = d[v] + 1;
			q.push(to);
			if (U[id] != v) swap(U[id], V[id]);
			was[id] = 1;
			order.emplace_back(id);
		}
	}
}

int solve(int root) {
	was.assign(M, 0);
	assert((int)was.size() == M);
	order.clear();
	bfs(root);
	vector<int>nu;
	for (int i = 0 ; i < M ; ++ i) {
		if (!was[i]) nu.emplace_back(i);
	}
	ll emp = Ask(nu);
	assert((int)order.size() == N-1);
	for (int i : order) cerr << i << " ";
	cerr << ": order\n";
	for (int i : nu) cerr << i << " ";
	cerr << ": nu\n";
	int l = 0, r = N - 2;
	while (l < r) {
		int m = (l + r + 1) / 2;
		vector<int>cur;
		for (int i = m ; i < N-1 ; ++ i) cur.emplace_back(order[i]);
		if (Ask(cur, nu) != emp) {
			l = m;
		} else {
			r = m - 1;
		}
	}
	l = order[l];
	int S = d[U[l]] > d[V[l]] ? U[l] : V[l];
	return S;
}

void find_pair(int N_, vector<int> U_, vector<int> V_, int A, int B) {
	M = U_.size();
	N = N_;
	U = U_;
	V = V_;
	cerr << N << " " << M << " " << A << " " << B << " given\n";
	for (int i = 0 ; i < M ; ++ i) {
		g[U[i]].emplace_back(V[i], i);
		g[V[i]].emplace_back(U[i], i);
	}
	int S = solve(0);
	int T = solve(S);
	cerr << S << " " << T << " mine\n";
	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