Submission #123905

#	Time	Username	Problem	Language	Result	Execution time	Memory
123905		nvmdava	Highway Tolls (IOI18_highway)	C++17	100 / 100	373 ms	10596 KiB

highway

#include "highway.h"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define pb push_back
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005], path, w;
long long def;
int p[100005], cat[100005];
vector<int> com[3];
int solve(vector<int>& ve){
	reverse(ve.begin(), ve.end());
	int l = 0, r = ve.size() - 1;
	while(l != r){
		int m = (l + r) >> 1;
		FOR(i, 0, m)
			w[p[ve[i]]] = 1;
		if(ask(w) > def) r = m;
		else l = m + 1;
		for(int i = 0; i <= m; i++)
			w[p[ve[i]]] = 0;
	}
	return ve[l];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	FOR(i, 0, m - 1){
		adj[U[i]].pb(i);
		adj[V[i]].pb(i);
		path.push_back(V[i] + U[i]);
	}
	w = vector<int>(m, 0);
	def = ask(w);	
	int l = 0, r = m - 1;
	while(l != r){
		int mm = (l + r) >> 1;
		FOR(i, 0, mm)
			w[i] = 1;
		if(ask(w) > def) r = mm;
		else l = mm + 1;
		FOR(i, 0, mm)
			w[i] = 0;
	}
	
	queue<pair<int, int> > q;
	q.push({V[l], 1});
	q.push({U[l], 2});
	cat[V[l]] = 1;
	p[V[l]] = l;
	p[U[l]] = l;
	cat[U[l]] = 2;
	com[1].push_back(V[l]);
	com[2].push_back(U[l]);
	while(!q.empty()){
		int u = q.front().first, t = q.front().second;
		q.pop();
		for(int x : adj[u]){
			int e = path[x] - u; 
			if(cat[e]) continue;
			cat[e] = t;
			com[t].push_back(e);
			p[e] = x;
			q.push({e, t});
		}
	}
	FOR(i, 0, m - 1)
		w[i] = 1;
	FOR(i, 0, N - 1)
		w[p[i]] = 0;
	answer(solve(com[1]), solve(com[2]));
}

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