Submission #423747

#	Time	Username	Problem	Language	Result	Execution time	Memory
423747		Pbezz	Werewolf (IOI18_werewolf)	C++14	0 / 100	4070 ms	95828 KiB

werewolf

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

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
vector<vector<ll>>adj(MAXN);
ll arr[MAXN],position[MAXN];
vector<vector<ll>>seg(4*MAXN);

void recalculate(ll node){
//seg[node].resize(0);
for(auto u:seg[2*node+1]){
seg[node].pb(u);
}
for(auto u:seg[2*node+2]){
seg[node].pb(u);
}
sort(seg[node].begin(),seg[node].end());
}

void build(ll node, ll left, ll right){

if(left==right){
seg[node].pb(arr[left]);
}else{
ll middle=(left+right)/2;

build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}

ll querie(ll node, ll left, ll right, ll a, ll b, ll c){

if(a<=left&&b>=right){
ll k=upper_bound(seg[node].begin(),seg[node].end(),c)-seg[node].begin();
//cout<<left<<" "<<right<<" "<<c<<endl;
return k;
}else{

ll middle=(left+right)/2,res=0;

if(a<=middle)res+=querie(2*node+1,left,middle,a,b,c);
if(b>=middle+1)res+=querie(2*node+2,middle+1,right,a,b,c);

return res;
}
}





void dfs(ll node, ll p,ll pos){
arr[pos]=node;
position[node]=pos;
for(auto u:adj[node]){

if(u==p)continue;

dfs(u,node,pos+1);
}
}

std::vector<int> check_validity(int N,std::vector<int>X,std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int Q = S.size(),m=(int)X.size(), i,n=N;

	for(i=0;i<m;i++){
	adj[X[i]].pb(Y[i]);
	adj[Y[i]].pb(X[i]);
	}

	for(i=0;i<N;i++){
	if(adj[i].size()==1)break;
	}

	dfs(i,-1,1);

	build(0,1,n);

	int s,e,l,r; ll lo,hi,mid;
	std::vector<int> A(Q);
	for(i=0;i<Q;i++){//cout<<"haha";

	s=S[i]; e=E[i]; l=L[i]; r=R[i];

	if(s<l||e>r){
	A[i]=0;
	continue;
	}
//	cout<<position[s]<<" "<<position[e]<<endl;
	if(position[s]<position[e]){//cout<<"hihi";

	//saber qual a leftmost pos com arr[pos] < l 
	hi=position[e];lo=position[s];

	if( querie(0,1,n,lo,hi,l-1)==0 ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){

	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,lo,mid,l-1)==0 ){
	lo=mid;
	}else{
	hi=mid;
	}

	}

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,l-1)==1 ){
	break;
	}
	}
	ll m1=mid-1;
	//human so pode andar entre position[e] e mid-1


	//saber qual a rightmost pos com arr[pos] > r 
	hi=position[e];lo=position[s];

	if( querie(0,1,n,lo,hi,r)==(hi-lo+1) ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){

	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,mid,hi,r)==(hi-mid+1) ){
	hi=mid;
	}else{
	lo=mid;
	}

	}

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,r)==0 ){
	break;
	}
	}
	ll m2=mid+1;
	//human so pode andar entre position[e] e mid-1
	A[i]=0;
	if(m1>=m2){
	A[i]=1;
	}
	//cout<<m1<<" "<<m2<<endl;
	}else{




	//saber qual a leftmost pos com arr[pos] > r
	lo=position[e]; hi=position[s];

	if( querie(0,1,n,lo,hi,r)==(hi-lo+1) ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){

	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,lo,mid,r)==(mid-lo+1) ){
	lo=mid;
	}else{
	hi=mid;
	}

	}

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,r)==0 ){
	break;
	}
	}
	ll m1=mid-1;
	//human so pode andar entre position[e] e mid-1


	//saber qual a rightmost pos com arr[pos] <l 
	hi=position[s];lo=position[e];

	if( querie(0,1,n,lo,hi,l-1)==0 ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){

	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,mid,hi,l-1)==0 ){
	hi=mid;
	}else{
	lo=mid;
	}

	}

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,l-1)==1 ){
	break;
	}
	}
	ll m2=mid+1;
	//human so pode andar entre position[e] e mid-1
	A[i]=0;
	if(m1>=m2){
	A[i]=1;
	}





}



}
  return A;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51