제출 #295253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295253		amoo_safar	통행료 (IOI18_highway)	C++17	51 / 100	269 ms	15056 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

vector<pii> G[N];
int E[N], dep[N];

void DFS(int u, int p, int d){
	//vis.pb(u);
	dep[u] = d;
	for(auto [adj, id] : G[u]){
		if(adj == p) continue;
		E[adj] = id;
		DFS(adj, u, d + 1);
	}
}

void find_pair(int _n, vector<int> U, vector<int> V, int A, int B){
	int n = _n;
	int m = U.size();
	assert(m == n - 1);
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	vector<int> W(m, 0);
	ll dis = ask(W);
	DFS(0, -1, 0);
	vector<int> I(n);
	iota(all(I), 0);
	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});
	/*
	cerr << "^ ";
	for(auto x : I)
		cerr << x << ' ';
	cerr << '\n';
	*/
	int st = -1, fn = -1;
	int L = 0, R = n - 1;

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) W[E[I[i]]] = 1;
		if(ask(W) > dis) R = mid;
		else L = mid;
	}
	st = I[L];
	//cerr << "! " << st << ' ' << L << '\n';
	DFS(st, -1, 0);
	iota(all(I), 0);
	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});
	L = 0, R = n - 1;

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) W[E[I[i]]] = 1;
		if(ask(W) > dis) R = mid;
		else L = mid;
	}
	fn = I[L];

	answer(st, fn);
}

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