Submission #298896

#	Time	Username	Problem	Language	Result	Execution time	Memory
298896		amiratou	Highway Tolls (IOI18_highway)	C++14	12 / 100	178 ms	11956 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MX = 90005;
#define sz(x) (ll)(x.size())
#define fi first
#define se second
typedef pair<ll,ll> ii;

vector<ii> vec[MX];
bitset<MX> vis,dead;
vector<ll> order,h;
ll d[MX],W[MX],p[MX];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for (ll i = 0; i < N-1; ++i)
	{
		vec[U[i]].push_back({V[i],i});
		vec[V[i]].push_back({U[i],i});
	}
	queue<ll> q;
	q.push(0);
	vis[0]=1;
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(!vis[it.fi]){
				d[it.fi]=d[f]+1;
				//cerr<<it.fi<<","<<d[it.fi]<<"\n";
				vis[it.fi]=1,q.push(it.fi);
				order.push_back(it.se);
			}
		}
	}
	//cerr<<"zero "<<d[0]<<"\n";
	for (ll i = 0; i < N-1; ++i)
		if(d[U[i]]>d[V[i]])swap(U[i],V[i]);
	vector<int> query(N-1,0);
	ll l=0,r=N-2,K=ask(query),ans=-1;
	while(l<=r){
		fill(query.begin(),query.end(),0);
		ll med=(l+r)>>1;
		for (ll i = 0; i < med; ++i)
			query[order[i]]=1;
		if(ask(query)==K)ans=med,l=med+1;
		else r=med-1;
	}
	ll lca=U[order[ans]];
	q.push(lca);
	order.clear();
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(d[it.fi]<d[f])continue;
			q.push(it.fi);
			p[it.fi]=f;
			W[it.fi]=it.se;
			order.push_back(it.se);
		}
	}
	/*cerr<<"LCA : "<<lca<<"\n";
	for(auto it:order){
		cerr<<U[it]<<"-"<<V[it]<<"\n";
	}*/
	l=0,r=sz(order)-1,ans=-1;
	while(l<=r){
		fill(query.begin(),query.end(),1);
		ll med=(l+r)>>1;
		for (ll i = 0; i <= med; ++i)
			query[order[i]]=0;
		if(ask(query)==K)ans=med,r=med-1;
		else l=med+1;
	}
	ll T=V[order[ans]];
	if(d[T]==(K/A)){answer(lca,T);return ;}
	ll node=T;
	while(node!=lca){
		//cerr<<node<<"\n";
		dead[node]=1;
		h.push_back(W[node]);
		node=p[node];
	}
	q.push(lca);
	order.clear();
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(d[it.fi]<d[f] ||dead[it.fi])continue;
			q.push(it.fi);
			order.push_back(it.se);
		}
	}
	l=0,r=sz(order)-1,ans=-1;
	/*for(auto it:h){
		cerr<<U[it]<<"->"<<V[it]<<"\n";
	}*/
	while(l<=r){
		fill(query.begin(),query.end(),1);
		for(auto it:h)
			query[it]=0;
		ll med=(l+r)>>1;
		for (ll i = 0; i <= med; ++i)
			query[order[i]]=0;
		if(ask(query)==K)ans=med,r=med-1;
		else l=med+1;
	}
	answer(T,V[order[ans]]);

}

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