Submission #296251

#	Time	Username	Problem	Language	Result	Execution time	Memory
296251		PeppaPig	Highway Tolls (IOI18_highway)	C++14	51 / 100	222 ms	15068 KiB

highway

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

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;

int n, m, A, B;
int chk[N], par[N];
vector<int> u, v;
vector<pii> g[N];

void find_pair(int _n, vector<int> _u, vector<int> _v, int _A, int _B) {
	n = _n, m = (int)_u.size(), u = _u, v = _v, A = _A, B = _B;

	for(int i = 0; i < m; i++) {
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}

	int rot = 0;
	long mn_dist = ask(vector<int>(m));
	vector<int> ans;
	
	for(int _ = 0; _ < 2; _++) {
		queue<int> Q;
		vector<int> vec;

		memset(chk, 0, sizeof chk);

		Q.emplace(rot), chk[rot] = 1, par[rot] = rot;
		while(!Q.empty()) {
			int u = Q.front(); Q.pop();
			for(pii v : g[u]) if(!chk[v.x]) {
				chk[v.x] = 1, par[v.x] = u;
				vec.emplace_back(v.y);
				Q.emplace(v.x);
			}
		}

		reverse(vec.begin(), vec.end());

		//printf("rot = %d\n", rot);
		//for(int i : vec) printf("%d ", i);
		//printf("\n");

		int l = 0, r = (int)vec.size() - 1;
		while(l < r) {
			int mid = (l + r) >> 1;

			vector<int> now(m);
			for(int i = 0; i <= mid; i++) now[vec[i]] = 1;
			if(ask(now) > mn_dist) r = mid;
			else l = mid + 1;
		}

		int a = u[vec[r]], b = v[vec[r]];
		if(par[b] == a) swap(a, b);
		ans.emplace_back(rot = a);
	}
	//printf("answer = %d %d\n", ans[0], ans[1]);

	answer(ans[0], ans[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