oj.uz

Submission #139076

# Submission time Handle Problem Language Result Execution time Memory
139076 2019-07-31T09:02:23 Z ckodser Highway Tolls (IOI18_highway) C++14
12 / 100
 534 ms 17916 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];
		}
	}
}
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;
}
void dfs(ll a){
	dfssz(a);
	ll cn=findCn(a,sz[a]/2);
	dfssz(cn);
	vector<int> w(m);
	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){
		
	}else{

	}
}*/
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);
	pii e=findAnsRot(0);
	answer(e.F,e.S);
	return ;
//	dfs(0);

}

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++){
                            ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5056 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5052 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5136 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 5044 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 22 ms 6408 KB Output is correct
3 Correct 217 ms 16992 KB Output is correct
4 Correct 299 ms 17044 KB Output is correct
5 Correct 353 ms 17036 KB Output is correct
6 Correct 250 ms 16992 KB Output is correct
7 Correct 250 ms 16980 KB Output is correct
8 Correct 389 ms 16992 KB Output is correct
9 Correct 271 ms 16988 KB Output is correct
10 Correct 220 ms 16972 KB Output is correct
11 Correct 226 ms 17476 KB Output is correct
12 Correct 534 ms 17916 KB Output is correct
13 Correct 511 ms 17652 KB Output is correct
14 Correct 479 ms 17152 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6820 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 24 ms 6392 KB Output is correct
3 Incorrect 114 ms 14380 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 5116 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 21 ms 5112 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -