Submission #1026189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026189		Lalic	Highway Tolls (IOI18_highway)	C++17	51 / 100	225 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 9e4+10;

int depth[MAXN], id[MAXN];
vector<pii> adj[MAXN];

void dfs(int ver, int prev){
	depth[ver]=depth[prev]+1;
	
	for(auto [u, v] : adj[ver]){
		if(u==prev) continue;
		id[u]=v;
		dfs(u, ver);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M=(int)U.size();
	
	for(int i=0;i<M;i++){
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	
	vector<int> w(M, 0);
	ll comp=ask(w);
	
	dfs(0, 0);
	
	vector<int> proc(N);
	iota(all(proc), 0);
	
	sort(all(proc), [&](int a, int b){ return depth[a]>depth[b]; });
	
	int low=0, high=N-2, best=-1;
	while(low<=high){
		int mid=(low+high)>>1;
		
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=1;
		ll curr=ask(w);
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=0;
		
		if(curr>comp){
			best=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	
	int s=proc[best];
	
	depth[s]=0;
	dfs(s, s);
	
	sort(all(proc), [&](int a, int b){ return depth[a]>depth[b]; });
	
	low=0; high=N-2; best=-1;
	while(low<=high){
		int mid=(low+high)>>1;
		
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=1;
		ll curr=ask(w);
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=0;
		
		if(curr>comp){
			best=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	
	int t=proc[best];
	
	answer(s, t);
}

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