oj.uz

답안 #424382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424382 2021-06-11T20:59:46 Z Pbezz 늑대인간 (IOI18_werewolf) C++14
34 / 100
 2647 ms 50708 KB 
#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],seg[4*MAXN][2];
//seg[i][0]=min
//vector<vector<ll>>seg(4*MAXN);

void recalculate(ll node){
//seg[node].resize(0);

seg[node][0]=min(seg[2*node+1][0],seg[2*node+2][0]);

seg[node][1]=max(seg[2*node+1][1],seg[2*node+2][1]);
}

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

if(left==right){
seg[node][0]=arr[left];
seg[node][1]=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 type){

if(a<=left&&b>=right){
return seg[node][type];
}else{

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

if(type==1){
if(a<=middle)res=max(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=max(res,querie(2*node+2,middle+1,right,a,b,type));
}else{res=INF;
if(a<=middle)res=min(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=min(res,querie(2*node+2,middle+1,right,a,b,type));
}
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,m1,m2;

	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<<i<<"\n";

	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,0)>=l ){//cout<<"kk ";
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

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

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,0)<l ){
	break;
	}
	}
	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,1)<=r ){//cout<<"gaga";
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

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

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,1)>r ){
	break;
	}
	}
	m2=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,1)<=r ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

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

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,1)>r ){
	break;
	}
	}
	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,0)>=l ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

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

	}

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,0)<l ){
	break;
	}
	}
	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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 32152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 32152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2647 ms 50584 KB Output is correct
2 Correct 836 ms 50628 KB Output is correct
3 Correct 842 ms 50612 KB Output is correct
4 Correct 1243 ms 50664 KB Output is correct
5 Correct 1525 ms 50664 KB Output is correct
6 Correct 2159 ms 50632 KB Output is correct
7 Correct 2545 ms 50604 KB Output is correct
8 Correct 817 ms 50612 KB Output is correct
9 Correct 640 ms 50660 KB Output is correct
10 Correct 625 ms 50708 KB Output is correct
11 Correct 792 ms 50592 KB Output is correct
12 Correct 1559 ms 50612 KB Output is correct
13 Correct 1763 ms 50536 KB Output is correct
14 Correct 1793 ms 50612 KB Output is correct
15 Correct 1680 ms 50608 KB Output is correct
16 Correct 1805 ms 50528 KB Output is correct
17 Correct 2567 ms 50612 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 32152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -