Submission #423015

#	Time	Username	Problem	Language	Result	Execution time	Memory
423015		amoo_safar	Highway Tolls (IOI18_highway)	C++17	51 / 100	333 ms	13968 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 BFS(int u){
	int adj;
	mk[u] = 1;
	vis.pb(u);
	int po = 0;
	while(po < (int) vis.size()){
		
		for(int ed : G[ vis[po] ]){
			if(ed >= bound)
				continue;
			adj = U[ed] ^ V[ed] ^ vis[po];
			if(mk[adj])
				continue;
			mk[adj] = 1;
			vis.pb(adj);
		}
		po++;
	}
}

int sm = 0;

int Solve(int u){
	memset(mk, 0, sizeof mk);
	vis.clear();
	BFS(u);
	sm += vis.size();
	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];
	int a1 = Solve(u);
	int a2 = Solve(v);
	answer(a1, a2);

	// 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