Submission #1131241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131241		StefanSebez	Highway Tolls (IOI18_highway)	C++20	100 / 100	222 ms	30792 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=130050,inf=1e9;
vector<pair<pair<int,int>,int>>edges;
int Idx(int u,int v){
	if(u>v)swap(u,v);
	pair<pair<int,int>,int>nesto={{u,v},0};
	int lb=lower_bound(edges.begin(),edges.end(),nesto)-edges.begin();
	return edges[lb].se;
}
vector<int>E[N];
vector<int>temp;
int n,m;ll D,A,B;
vector<int>E1[N],E2[N];
vector<int>grane1,grane2;
int depth1[N],depth2[N];
int strana[N];
void DFS1(int u,int parent=-1){
	for(auto i:E1[u]){
		if(i==parent||strana[i]==2) continue;
		grane1.pb(Idx(u,i));
		DFS1(i,u);
	}
}
void DFS2(int u,int parent=-1){
	for(auto i:E2[u]){
		if(i==parent||strana[i]==1) continue;
		grane2.pb(Idx(u,i));
		DFS2(i,u);
	}
}
void find_pair(int n1, std::vector<int> U, std::vector<int> V, int A1, int B1){
	n=n1,m=U.size(),A=A1,B=B1;
	for(int i=0;i<m;i++){int u=U[i],v=V[i];if(u>v) swap(u,v);edges.pb({{u,v},i});E[u].pb(v),E[v].pb(u);}
	sort(edges.begin(),edges.end());
	temp.resize(m);for(int i=0;i<m;i++) temp[i]=0;
	D=ask(temp)/A;
	int l=0,r=m-1;
	int u,v,Ind;
	while(l<=r){
		int mid=l+r>>1;
		for(int i=0;i<m;i++) temp[i]=0;
		for(int i=0;i<=mid;i++) temp[i]=1;
		ll x=ask(temp);
		if(x>D*A){u=U[mid],v=V[mid],Ind=mid;r=mid-1;}
		else l=mid+1;
	}
	queue<int>kju;
	kju.push(u);
	for(int i=0;i<n;i++) depth1[i]=inf;depth1[u]=0;
	while(!kju.empty()){
		int c=kju.front();kju.pop();
		for(auto i:E[c]){
			if(depth1[i]<=depth1[c]+1) continue;
			depth1[i]=depth1[c]+1;
			E1[c].pb(i);
			kju.push(i);
		}
	}
	kju.push(v);
	for(int i=0;i<n;i++) depth2[i]=inf;depth2[v]=0;
	while(!kju.empty()){
		int c=kju.front();kju.pop();
		for(auto i:E[c]){
			if(depth2[i]<=depth2[c]+1) continue;
			depth2[i]=depth2[c]+1;
			E2[c].pb(i);
			kju.push(i);
		}
	}
	for(int i=0;i<n;i++) strana[i]=depth1[i]<depth2[i]?1:2;
	DFS1(u);
	DFS2(v);
	l=0,r=grane1.size();
	int S=u,T=v;
	while(l<=r){
		int mid=l+r>>1;
		for(int i=0;i<m;i++) temp[i]=1;
		for(auto i:grane2) temp[i]=0;
		temp[Ind]=0;
		for(int i=0;i<grane1.size();i++) temp[grane1[i]]=(i+1<=mid)?0:1;
		ll x=ask(temp);
		if(x>A*D) l=mid+1;
		else{
			r=mid-1;
			if(mid==0){S=u;continue;}
			S=grane1[mid-1];
			if(depth1[U[S]]>depth1[V[S]]) S=U[S];
			else S=V[S];
		}
	}
	l=0,r=grane2.size();
	while(l<=r){
		int mid=l+r>>1;
		for(int i=0;i<m;i++) temp[i]=1;
		for(auto i:grane1) temp[i]=0;
		temp[Ind]=0;
		for(int i=0;i<grane2.size();i++) temp[grane2[i]]=(i+1<=mid)?0:1;
		ll x=ask(temp);
		if(x>A*D) l=mid+1;
		else{
			r=mid-1;
			if(mid==0){T=v;continue;}
			T=grane2[mid-1];
			if(depth2[U[T]]>depth2[V[T]]) T=U[T];
			else T=V[T];
		}
	}
	answer(S,T);
}

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