oj.uz

Submission #139060

# Submission time Handle Problem Language Result Execution time Memory
139060 2019-07-31T08:53:35 Z ckodser Highway Tolls (IOI18_highway) C++14
12 / 100
 555 ms 17048 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;
	for(ll i=0;i<(ll)vec.size()/2;i++){
		l.pb(vec[i]);
	}	
	if(as(l,rot)==adi+b-a){
		return finds(l,rot);
	}
	l.clear();
	for(ll i=(ll)vec.size()/2;i<vec.size();i++){
		l.pb(vec[i]);
	}
	return finds(l,rot);
}
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);
	topol.pop_back();
	return mp(rot,finds(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:60: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 5032 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 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5052 KB Output is correct
7 Correct 6 ms 5048 KB Output is correct
8 Correct 6 ms 5044 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5080 KB Output is correct
11 Correct 6 ms 5048 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 5160 KB Output is correct
2 Correct 30 ms 6384 KB Output is correct
3 Correct 212 ms 16228 KB Output is correct
4 Correct 302 ms 16192 KB Output is correct
5 Correct 319 ms 16200 KB Output is correct
6 Correct 250 ms 16228 KB Output is correct
7 Correct 244 ms 16252 KB Output is correct
8 Correct 317 ms 16244 KB Output is correct
9 Correct 249 ms 16252 KB Output is correct
10 Correct 221 ms 16252 KB Output is correct
11 Correct 215 ms 16760 KB Output is correct
12 Correct 531 ms 17048 KB Output is correct
13 Correct 555 ms 16944 KB Output is correct
14 Correct 482 ms 16412 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 6716 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 Incorrect 7 ms 5196 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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