Submission #422979

#	Time	Username	Problem	Language	Result	Execution time	Memory
422979		amoo_safar	Highway Tolls (IOI18_highway)	C++17	51 / 100	221 ms	16288 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int n, m;
ll dis;

vector<int> G[N], U, V;

int bound;

vector<int> vis;
int mk[N];
void DFS(int u){
	mk[u] = 1;
	int adj;
	vis.pb(u);
	for(int ed : G[u]){
		if(ed >= bound)
			continue;
		adj = U[ed] ^ V[ed] ^ u;
		if(mk[adj])
			continue;
		DFS(adj);
	}
}

int Solve(int u){
	memset(mk, 0, sizeof mk);
	V.clear();
	DFS(u);
	reverse(vis.begin(), vis.end());
	int sz = vis.size();
	int lw = 0, hg = sz, mid;
	while(lw + 1 < hg){
		mid = (lw + hg) >> 1;
		memset(mk, 0, sizeof mk);
		for(int i = 0; i < mid; i++)
			mk[vis[i]] = 1;
		vector<int> w;
		for(int i = 0; i < m; i++)
			w.pb(mk[U[i]] || mk[V[i]] || (i > bound));
		if(ask(w) == dis)
			lw = mid;
		else 
			hg = mid;
	}
	return vis[lw];
}
void find_pair(int _n, vector<int> _U, vector<int> _V, int A, int B) {
	n = _n;
	U = _U;
	V = _V;

	m = U.size();
	for(int i = 0; i < m; i++) G[U[i]].pb(i), G[V[i]].pb(i);
	
	vector<int> w(m, 0);
	dis = ask(w);
	{
		int lw = 0, hg = m;
		int mid;
		while(lw + 1 < hg){
			mid = (lw + hg) >> 1;
			vector<int> as(mid, 0);
			as.resize(m, 1);
			if(ask(as) == dis)
				hg = mid;
			else
				lw = mid;
		}
		bound = lw;
	}
	int u = U[bound];
	int v = V[bound];
	answer(Solve(u), Solve(v));
	// int M = U.size();
	// for (int j = 0; j < 50; ++j) {
	// 	std::vector<int> w(M);
	// 	for (int i = 0; i < M; ++i) {
	// 		w[i] = 0;
	// 	}
	// 	long long toll = ask(w);
	// }
	// answer(0, N - 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