Submission #1068018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068018		UmairAhmadMirza	Highway Tolls (IOI18_highway)	C++17	0 / 100	18 ms	7508 KiB

highway

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void answer(int s, int t);
long long ask(const vector<int> &w);

int const MAXN=90005;

vector<pair<int,int>> adj[MAXN];
int par_ind[MAXN];
int dep[MAXN];
vector<int> di[MAXN];
int n,a,b,m;
vector<int> col;

void dfs(int node,int par){
	dep[node]=dep[par]+1;
	di[dep[node]].push_back(node);
	for(auto [i,e]:adj[node])
		if(i!=par){
			par_ind[i]=e;
			dfs(i,node);
		}
}

int solve(int s){
	for (int i = 0; i < n; ++i){
		di[i].clear();
		dep[i]=0;
	}
	dfs(s,0);
	ll sm=ask(col);
	ll k=sm/a;
	k++;
	int ln=di[k].size();
	int low=0,high=ln;
	while(high-low>1){
		int mid=(high+low)/2;
		for(int i=0;i<m;i++)
			col[i]=0;
		for(int i=low;i<mid;i++)
			col[par_ind[di[k][i]]]=1;
		if(ask(col)>sm)
			high=mid;
		else
			low=mid;
	}
	return di[k][low];
}
int pre_solver(){
	dfs(0,0);
	ll sm=ask(col);
	ll k=sm/a;
	k++;
	int low=2,high=n;
	while(high-low>1){
		int mid=(high+low)/2;
		for(int i=0;i<m;i++)
			col[i]=0;
		for(int i=mid;i<high;i++)
			for(int j:di[i])
				col[par_ind[j]]=1;
		if(ask(col)>sm)
			low=mid;
		else
			high=mid;
	}
	return di[low][0];
}
void find_pair(int nn, vector<int> U, vector<int> V, int A, int B){
	// cout<<"In"<<endl;
	n=nn;
	a=A;
	b=B;
	m=U.size();
	if(m!=n-1)
		return;
	col.resize(m);
	for(int i=0;i<m;i++){
		col[i]=0;
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}

	int s=pre_solver();
	int t=solve(s);
	// cout<<s<<' '<<t<<endl;
	answer(s,t);
}

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