Submission #1071200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071200		Dan4Life	Highway Tolls (IOI18_highway)	C++17	51 / 100	171 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ar2 = array<int,2>;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int mxN = (int)2e5+10;
int n, m, dep[mxN];
ll A, B, dis;
int st[mxN], dfs_tim;
vector<ar2> adj[mxN], potential_edges;
vi w, edges;

void init(){
	dfs_tim = 0;
	edges.clear();
	potential_edges.clear();
}

void dfs(int s, int p){
	st[s] = dfs_tim++;
	if(p!=-1) dep[s] = dep[p]+1;
	else dep[s] = 0;
	for(auto [u,i] : adj[s]){
		if(u==p) continue;
		edges.pb(i); dfs(u,s);
		if(dep[s]+1==dis) potential_edges.pb({i,u});
	}
}

bool chk(int x){
	for(int i = sz(edges)-1; i >= x; i--) w[edges[i]]=1;
	ll toll = ask(w);
	for(int i = sz(edges)-1; i >= x; i--) w[edges[i]]=0;
	return (toll!=A*dis);
}

bool chk2(int x){
	for(int i = 0; i <= x; i++) w[potential_edges[i][0]]=1;
	ll toll = ask(w);
	for(int i = 0; i <= x; i++) w[potential_edges[i][0]]=0;
	return (toll!=A*dis);
}

void find_pair(int N, vi U, vi V, int _A, int _B) {
	n = N, m = sz(U); w.resize(m,0); 
	A=_A, B=_B; dis = ask(w)/A;
	for(int i = 0; i < m; i++){
		int a = U[i], b = V[i];
		adj[a].pb({b,i}); 
		adj[b].pb({a,i});
	}
	
	init(); dfs(0,-1);
	int s=0, t=0;
	int l = 0, r = sz(edges)-1;
	while(l<r){
		int mid = (l+r+1)/2;
		if(chk(mid)) l=mid;
		else r=mid-1;
	}
	s = edges[l];
	if(st[U[s]] > st[V[s]]) s=U[s];
	else s=V[s];
	init(); dfs(s,-1);
	l = 0, r = sz(potential_edges)-1;
	while(l<r){
		int mid = (l+r)/2;
		if(chk2(mid)) r=mid;
		else l=mid+1;
	}
	t = potential_edges[l][1];
	if(s>t) swap(s,t);
	answer(s, t); return;
}

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