oj.uz

Submission #139100

# Submission time Handle Problem Language Result Execution time Memory
139100 2019-07-31T09:24:24 Z ckodser Highway Tolls (IOI18_highway) C++14
51 / 100
 799 ms 21504 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5044 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 5144 KB Output is correct
5 Correct 6 ms 5052 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 5048 KB Output is correct
8 Correct 6 ms 5048 KB Output is correct
9 Correct 6 ms 5044 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5032 KB Output is correct
12 Correct 6 ms 5052 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5160 KB Output is correct
2 Correct 32 ms 6280 KB Output is correct
3 Correct 337 ms 14728 KB Output is correct
4 Correct 427 ms 17712 KB Output is correct
5 Correct 458 ms 17700 KB Output is correct
6 Correct 378 ms 17696 KB Output is correct
7 Correct 335 ms 17664 KB Output is correct
8 Correct 267 ms 14844 KB Output is correct
9 Correct 360 ms 17672 KB Output is correct
10 Correct 315 ms 15100 KB Output is correct
11 Correct 332 ms 15012 KB Output is correct
12 Correct 515 ms 16808 KB Output is correct
13 Correct 458 ms 16388 KB Output is correct
14 Correct 578 ms 17788 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6312 KB Output is correct
2 Correct 46 ms 8184 KB Output is correct
3 Correct 83 ms 8724 KB Output is correct
4 Correct 195 ms 21504 KB Output is correct
5 Correct 169 ms 16452 KB Output is correct
6 Correct 215 ms 21472 KB Output is correct
7 Correct 171 ms 16380 KB Output is correct
8 Correct 189 ms 21336 KB Output is correct
9 Correct 179 ms 18896 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5164 KB Output is correct
2 Correct 35 ms 6496 KB Output is correct
3 Correct 160 ms 11920 KB Output is correct
4 Correct 234 ms 14332 KB Output is correct
5 Correct 256 ms 13896 KB Output is correct
6 Correct 221 ms 14016 KB Output is correct
7 Correct 239 ms 12764 KB Output is correct
8 Correct 264 ms 13124 KB Output is correct
9 Correct 417 ms 17704 KB Output is correct
10 Correct 462 ms 17712 KB Output is correct
11 Correct 419 ms 17760 KB Output is correct
12 Correct 712 ms 18592 KB Output is correct
13 Correct 554 ms 18432 KB Output is correct
14 Correct 349 ms 16504 KB Output is correct
15 Correct 231 ms 13748 KB Output is correct
16 Correct 274 ms 12992 KB Output is correct
17 Correct 546 ms 18424 KB Output is correct
18 Correct 399 ms 15628 KB Output is correct
19 Correct 244 ms 13280 KB Output is correct
20 Correct 279 ms 15588 KB Output is correct
21 Correct 279 ms 17864 KB Output is correct
22 Correct 247 ms 17976 KB Output is correct
23 Correct 240 ms 17920 KB Output is correct
24 Correct 360 ms 18372 KB Output is correct
25 Correct 799 ms 20888 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 5112 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 5116 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -