oj.uz

답안 #406315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406315 2021-05-17T11:04:25 Z Antekb 늑대인간 (IOI18_werewolf) C++14
34 / 100
 438 ms 42768 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef vector<int> vi;
const int N=(1<<18);
vi E[N];
int wsk;
int vis[N], pre[N], tab[N+N], tab2[N+N];
void dfs(int v){
	vis[v]=1;
	tab[N+wsk]=v;
	tab2[N+wsk]=v;
	pre[v]=wsk++;
	for(int u:E[v]){
		if(!vis[u]){
			dfs(u);	
		}
	}
}
int lstmax(int l, int r, int c){
	//cout<<"a "<<l<<" "<<r<<" "<<c<<"\n";
	r++;
	int lew=-1;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			if(tab[l]>=c){
				lew=l;
			}
			l++;
		}
		if(r&1){
			if(tab[--r]>=c){
				while(r<N){
					if(tab[r+r+1]>=c)r=r+r+1;
					else r=r+r;
				}
				return r;
			}
		}
	}
	if(lew==-1)return -N-N;
	r=lew;
	while(r<N){
		if(tab[r+r+1]>=c)r=r+r+1;
		else r=r+r;
	}
	return r;
}
int fstmax(int l, int r, int c){
	//cout<<"b "<<l<<" "<<r<<" "<<c<<"\n";
	r++;
	int lew=-1;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			if(tab[l]>=c){
				while(l<N){
					if(tab[l+l]>=c)l=l+l;
					else l=l+l+1;
				}
				return l;
			}
			l++;
		}
		if(r&1){
			if(tab[--r]>=c){
				lew=r;
			}
		}
	}
	if(lew==-1)return N+N;
	l=lew;
	while(l<N){
		if(tab[l+l]>=c)l=l+l;
		else l=l+l+1;
	}
	return l;
}
int lstmin(int l, int r, int c){
//cout<<"c "<<l<<" "<<r<<" "<<c<<"\n";
	r++;
	int lew=-1;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			if(tab2[l]<=c){
				lew=l;
			}
			l++;
		}
		if(r&1){
			if(tab2[--r]<=c){
				while(r<N){
					if(tab2[r+r+1]<=c)r=r+r+1;
					else r=r+r;
				}
				return r;
			}
		}
	}
	if(lew==-1)return -N-N;
	r=lew;
	while(r<N){
		if(tab2[r+r+1]<=c)r=r+r+1;
		else r=r+r;
	}
	return r;
}
int fstmin(int l, int r, int c){
	//cout<<"d "<<l<<" "<<r<<" "<<c<<"\n";
	r++;
	int lew=-1;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			if(tab2[l]<=c){
				while(l<N){
					if(tab2[l+l]<=c)l=l+l;
					else l=l+l+1;
				}
				return l;
			}
			l++;
		}
		if(r&1){
			if(tab2[--r]<=c){
				lew=r;
			}
		}
	}
	if(lew==-1)return N+N;
	l=lew;
	while(l<N){
		if(tab2[l+l]<=c)l=l+l;
		else l=l+l+1;
	}
	return l;
}
std::vector<int> check_validity(int n, vi X, vi Y,
                                vi S, vi T,
                                vi L, vi R) {
    int m=X.size();
	for(int i=0; i<m; i++){
		E[X[i]].pb(Y[i]);
		E[Y[i]].pb(X[i]);
	}
	for(int i=0; i<n; i++){
		if(E[i].size()==1){
			dfs(i);
			break;
		}
	}
	for(int i=N-1; i>0; i--){
		tab[i]=max(tab[i+i], tab[i+i+1]);
		tab2[i]=min(tab2[i+i], tab2[i+i+1]);
	}
	int q = S.size();
	std::vector<int> A(q);
  	for (int i = 0; i < q; ++i){
  		if(pre[S[i]]<pre[T[i]]){
  			//cout<<"a";
  			int k=lstmax(pre[S[i]], pre[T[i]], R[i]+1), l=fstmin(pre[S[i]], pre[T[i]], L[i]-1);
  			//cout<<k-N<<" "<<l-N<<"\n";
  			A[i]=(k<l-1);
  		}
  		else{
  		//cout<<"b";
  			int k=fstmax(pre[T[i]], pre[S[i]], R[i]+1), l=lstmin(pre[T[i]], pre[S[i]], L[i]-1);
  			//cout<<k-N<<" "<<l-N<<"\n";
  			A[i]=(k>l+1);
  		}
	}
	return A;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 34364 KB Output is correct
2 Correct 438 ms 42760 KB Output is correct
3 Correct 379 ms 42756 KB Output is correct
4 Correct 364 ms 42692 KB Output is correct
5 Correct 376 ms 42768 KB Output is correct
6 Correct 367 ms 42640 KB Output is correct
7 Correct 400 ms 42756 KB Output is correct
8 Correct 382 ms 42768 KB Output is correct
9 Correct 297 ms 42764 KB Output is correct
10 Correct 325 ms 42632 KB Output is correct
11 Correct 328 ms 42628 KB Output is correct
12 Correct 310 ms 42732 KB Output is correct
13 Correct 359 ms 42764 KB Output is correct
14 Correct 354 ms 42752 KB Output is correct
15 Correct 350 ms 42692 KB Output is correct
16 Correct 352 ms 42756 KB Output is correct
17 Correct 382 ms 42692 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -