제출 #991608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991608		Lalic	늑대인간 (IOI18_werewolf)	C++17	49 / 100	425 ms	69924 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int INF = 0x3f3f3f3f;

int pai[2][MAXN], peso[2][MAXN];

int find(int tipo, int x){ return (pai[tipo][x]==x ? x : pai[tipo][x]=find(tipo, pai[tipo][x])); }
void join(int tipo, int a, int b){
	a=find(tipo, a);
	b=find(tipo, b);
	if(a==b) return;
	
	if(peso[tipo][a]>peso[tipo][b]) swap(a, b);
	pai[tipo][a]=b;
	peso[tipo][b]=max(peso[tipo][b], peso[tipo][a]+1);
}

int conv[MAXN], rev[MAXN];
vector<int> adj[MAXN];

void dfs(int ver, int val){
	conv[val]=ver;
	rev[ver]=val;
	for(auto u : adj[ver]){
		if(rev[u]!=-1) continue;
		dfs(u, val+1);
	}
}

int st[2][20][MAXN], lg[MAXN];

void build(int n){
	lg[0]=lg[1]=0;
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	
	for(int i=0;i<n;i++)
		st[0][0][i]=st[1][0][i]=conv[i];
	
	for(int i=1;i<=18;i++)
		for(int j=0;j<n;j++)
			st[0][i][j]=min(st[0][i-1][j], st[0][i-1][min(j+(1<<(i-1)), n)]);
	for(int i=1;i<=18;i++)
		for(int j=0;j<n;j++)
			st[1][i][j]=max(st[1][i-1][j], st[1][i-1][min(j+(1<<(i-1)), n)]);
}

int getMx(int l, int r){
	int curr=lg[r-l+1];
	return max(st[1][curr][l], st[1][curr][r-(1<<curr)+1]);
}

int getMn(int l, int r){
	int curr=lg[r-l+1];
	return min(st[0][curr][l], st[0][curr][r-(1<<curr)+1]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	int m=(int)X.size(), q=(int)L.size();
	vector<int> ans(q);
	
	if(N<=3000 && m<=6000 && q<=3000){
		for(int i=0;i<q;i++){
			for(int j=0;j<N;j++){
				pai[0][j]=pai[1][j]=j;
				peso[0][j]=peso[1][j]=0;
			}
			
			for(int j=0;j<m;j++){
				if(max(X[j], Y[j])<=R[i]) join(1, X[j], Y[j]);
				if(min(X[j], Y[j])>=L[i]) join(0, X[j], Y[j]);
			}
			
			ans[i]=0;
			for(int j=0;j<N;j++){
				if(find(0, S[i])==find(0, j) && find(1, E[i])==find(1, j)){
					ans[i]=1;
					break;
				}
			}
		}
	}
	else{
		memset(rev, -1, sizeof rev);
		for(int i=0;i<m;i++){
			adj[X[i]].pb(Y[i]);
			adj[Y[i]].pb(X[i]);
		}
		
		for(int i=0;i<N;i++){
			if((int)adj[i].size()==1){
				dfs(i, 0);
				break;
			}
		}
		
		build(N);
		
		for(int i=0;i<q;i++){
			int ini=rev[S[i]], fim=rev[E[i]];
			
			if(ini==fim) ans[i]=1;
			else if(ini<fim){
				int lastH=-1;
				if(getMx(ini, fim)>R[i]){
					int low=ini, high=fim;
					while(low<=high){
						int mid=(low+high)>>1;
						if(getMx(mid, fim)>R[i]){
							lastH=mid;
							low=mid+1;
						}
						else high=mid-1;
					}
				}
				
				int lastW=INF;
				if(getMn(ini, fim)<L[i]){
					int low=ini, high=fim;
					while(low<=high){
						int mid=(low+high)>>1;
						if(getMn(ini, mid)<L[i]){
							lastW=mid;
							high=mid-1;
						}
						else low=mid+1;
					}
				}
				
				if(lastH>lastW || lastW==lastH+1) ans[i]=0;
				else ans[i]=1;
			}
			else{
				int lastH=INF;
				if(getMx(fim, ini)>R[i]){
					int low=fim, high=ini;
					while(low<=high){
						int mid=(low+high)>>1;
						if(getMx(fim, mid)>R[i]){
							lastH=mid;
							high=mid-1;
						}
						else low=mid+1;
					}
				}
				
				int lastW=-1;
				if(getMn(fim, ini)<L[i]){
					int low=fim, high=ini;
					while(low<=high){
						int mid=(low+high)>>1;
						if(getMn(mid, ini)<L[i]){
							lastW=mid;
							low=mid+1;
						}
						else high=mid-1;
					}
				}
				
				if(lastH<lastW || lastW==lastH-1) ans[i]=0;
				else ans[i]=1;
			}
		}
	}
	return ans;
}

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