Submission #139100

#	Time	Username	Problem	Language	Result	Execution time	Memory
139100		ckodser	Highway Tolls (IOI18_highway)	C++14	51 / 100	799 ms	21504 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2e5+500;
const ll inf=1e9+900;
const ll mod=1e9+7;


vector<ll> ger[maxn];
bool hazf[maxn];
ll s[maxn];
ll t[maxn];
ll sz[maxn];
ll st[maxn];
ll et[maxn];
ll tt=0;
ll m,a,b,adi,n;
vector<int> w;


void dfsas(ll a,ll tim,ll p=-1){
	for(auto e:ger[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p && !hazf[v]){
			if(et[v]<=tim){
				w[e]=1;
				continue;
			}
			dfsas(v,tim,a);
		}
	}
}
ll as(vector<ll> vec,ll rot){
	w.clear();
	w.resize(m);
	fill(w.begin(),w.end(),0);
	dfsas(rot,et[vec.back()]);
	return ask(w);
}
ll finds(vector<ll> vec,ll rot){
	if(vec.size()==1)return  vec[0];
	vector<ll> l,r;
	for(ll i=0;i<(ll)vec.size()/2;i++){
		l.pb(vec[i]);
	}	
	for(ll i=(ll)vec.size()/2;i<vec.size();i++){
		r.pb(vec[i]);
	}
	if(as(l,rot)==adi+b-a){
		return finds(l,rot);
	}
	return finds(r,rot);
}
pii findst(vector<ll> vec,ll rot){
	if(vec.size()==2)return mp(vec[0],vec[1]);
	vector<ll> l,r;
	for(ll i=0;i<(ll)vec.size()/2;i++){
		l.pb(vec[i]);
	}	
	for(ll i=(ll)vec.size()/2;i<vec.size();i++){
		r.pb(vec[i]);
	}
	ll p=as(l,rot);
	if(p==adi+b-a+b-a){
		return findst(l,rot);
	}
	if(p==adi){
		return findst(r,rot);
	}
	ll fa=finds(l,rot);
	adi+=b-a;
	ll fb=finds(r,rot);
	return mp(fa,fb);
}
vector<ll> topol;
void dfsst(ll a,ll p=-1){
	st[a]=tt;
	for(auto e:ger[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p && !hazf[v]){
			dfsst(v,a);
		}
	}
	topol.pb(a);
	et[a]=tt;
	tt++;
}
pii findAnsRot(ll rot){
	tt=0;
	dfsst(rot);
	return findst(topol,rot);
}
void dfssz(ll a,ll p=-1){
	sz[a]=1;
	for(auto e:ger[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p && !hazf[v]){
			dfssz(v,a);
			sz[a]+=sz[v];
		}
	}
}
void dfs1(ll a,ll p=-1){
	for(auto e:ger[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p && !hazf[v]){
			w[e]=1;
			dfs1(v,a);
		}
	}
}
ll findCn(ll a,ll x,ll p=-1){
	for(auto e:ger[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p && !hazf[v] && sz[v]>x){
			return findCn(v,x,a);
		}
	}
	return a;
}
ll findYal(vector<ll> vec,ll cn){
	if(vec.size()==1)return  vec[0];
	vector<ll> l,r;
	for(ll i=0;i<(ll)vec.size()/2;i++){
		l.pb(vec[i]);
	}	
	for(ll i=(ll)vec.size()/2;i<vec.size();i++){
		r.pb(vec[i]);
	}
	fill(w.begin(),w.end(),0);
	for(auto v:l){
		dfs1(v,cn);
	}
	if(ask(w)==adi){
		return findYal(r,cn);
	}
	return  findYal(l,cn);
}
ll last;
pii dfs(ll a){
	dfssz(a);
	if(sz[a]>(last-1)/2)exit(1);;
	last=sz[a]+1;
	ll cn=findCn(a,sz[a]/2);
	dfssz(cn);
	w.resize(m);
	fill(w.begin(),w.end(),0);
	for(auto e:ger[cn]){
		ll v=(s[e]^t[e]^cn);
		if(!hazf[v]){
			w[e]=1;
		}
	}
	ll r=ask(w);
	if(r!=adi){
		return findAnsRot(cn);
	}
	hazf[cn]=1;
	
	vector<ll> vec;
	for(auto e:ger[cn]){
		ll v=(s[e]^t[e]^cn);
		if(!hazf[v]){
			vec.pb(v);
		}
	}
	return dfs(findYal(vec,cn));
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	a=A;
	b=B;
	m=V.size();
	n=N;
	if(m!=n-1){
		exit(1);
	}
	for(ll i=0;i<m;i++){
		s[i]=V[i];
		t[i]=U[i];
	}
	for(ll i=0;i<m;i++){
		ger[s[i]].pb(i);
		ger[t[i]].pb(i);
	}
	vector<int> w(m);
	fill(w.begin(),w.end(),0);
	adi=ask(w);
	last=2*n+1;
	pii e=dfs(0);
	answer(e.F,e.S);
}

Compilation message (stderr)

highway.cpp: In function 'long long int finds(std::vector<long long int>, long long int)':
highway.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(ll)vec.size()/2;i<vec.size();i++){
                            ~^~~~~~~~~~~
highway.cpp: In function 'std::pair<long long int, long long int> findst(std::vector<long long int>, long long int)':
highway.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(ll)vec.size()/2;i<vec.size();i++){
                            ~^~~~~~~~~~~
highway.cpp: In function 'long long int findYal(std::vector<long long int>, long long int)':
highway.cpp:137:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(ll)vec.size()/2;i<vec.size();i++){
                            ~^~~~~~~~~~~

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