oj.uz

답안 #139091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139091 2019-07-31T09:15:05 Z ckodser 통행료 (IOI18_highway) C++14
0 / 100
 137 ms 10964 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 last;
pii dfs(ll a){
	dfssz(a);
	if(sz[a]>(last-1)/2)exit(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;
	if(ger[cn].size()>2)exit(1);
	fill(w.begin(),w.end(),0);
	dfs1(ger[cn][0]);
	if(ask(w)==adi){
		return dfs(ger[cn][1]);
	}
	return dfs(ger[cn][0]);
}
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++){
                            ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5052 KB Output is correct
2 Correct 7 ms 5044 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Runtime error 6 ms 5052 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Runtime error 29 ms 5860 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 6264 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5124 KB Output is correct
2 Correct 29 ms 6496 KB Output is correct
3 Runtime error 137 ms 10964 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 5160 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 5112 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -