Submission #134264

#	Time	Username	Problem	Language	Result	Execution time	Memory
134264		MoNsTeR_CuBe	Werewolf (IOI18_werewolf)	C++17	15 / 100	398 ms	95604 KiB

werewolf

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

vector< int > v;

struct node{
	node* l, *r;
	int mini, maxi;
	
	void update(){
		mini = INT_MAX;
		maxi = INT_MIN;
		
		if(l){
			mini = min(mini, l->mini);
			maxi = max(maxi, l->maxi);
		}
		if(r){
			mini = min(mini, r->mini);
			maxi = max(maxi, r->maxi);
		}
	}
};

void Build(node* root, int left, int right){
	if(left == right){
		root->mini = root->maxi = v[left];
		return;
	}
	root->l = new node{NULL,NULL,0,0};
	root->r = new node{NULL,NULL,0,0};
	int mid = (left+right)/2;
	
	Build(root->l, left, mid);
	Build(root->r, mid+1, right);
	
	root->update();
}

int wolf_left(node* root, int left, int right, int qL, int qR, int val){

	if(left > qR || right < qL) return -1;
	
	if(left >= qL && right <= qR){
		if(root->maxi < val) return left;
	}
	
	int mid = (left+right)/2;
	if(wolf_left(root->r, mid+1, right, qL, qR, val) == mid+1){
		return wolf_left(root->l, left, mid, qL, qR, val);
	}
	return wolf_left(root->r, mid+1, right, qL, qR, val);
}

int wolf_right(node* root, int left, int right, int qL, int qR, int val){

	if(left > qR || right < qL) return -1;
	
	if(left >= qL && right <= qR){
		if(root->maxi < val) return right;
	}
	
	int mid = (left+right)/2;
	if(wolf_right(root->l, left, mid, qL, qR, val) == mid){
		return wolf_right(root->r, mid+1, right, qL, qR, val);
	}
	return wolf_right(root->l, left, mid, qL, qR, val);
}

int human_right(node* root, int left, int right, int qL, int qR, int val){

	if(left > qR || right < qL) return -1;
	
	if(left >= qL && right <= qR){
		if(root->mini > val) return right;
	}
	
	int mid = (left+right)/2;
	if(human_right(root->l, left, mid, qL, qR, val) == mid){
		return human_right(root->r, mid+1, right, qL, qR, val);
	}
	return human_right(root->l, left, mid, qL, qR, val);
}

int human_left(node* root, int left, int right, int qL, int qR, int val){

	if(left > qR || right < qL) return -1;
	
	if(left >= qL && right <= qR){
		if(root->mini > val) return left;
	}
	
	int mid = (left+right)/2;
	if(human_left(root->r, mid+1, right, qL, qR, val) == mid+1){
		return human_left(root->l, left, mid, qL, qR, val);
	}
	return human_left(root->r, mid+1, right, qL, qR, val);
}

pair<int, int> query(node* root, int left, int right, int qL, int qR){
	if(left > qR || right < qL) return {INT_MAX, INT_MIN};
	if(left >= qL && right <= qR) return {root->mini, root->maxi};
	int mid = (left+right)/2;
	
	pair<int, int> L = query(root->l, left, mid, qL, qR);
	pair<int, int> R = query(root->r, mid+1, right, qL, qR);
	
	return {min(L.first, R.first), max(L.second, R.second)};
}

///////////////////////////////////////////////////////////////////////

void dfs(vector< vector< int > >& Graph, int last, int nodee){
	v.push_back(nodee);
	for(int a : Graph[nodee]){
		if(a == last) continue;
		dfs(Graph, nodee, a);
	}
}

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 Q = S.size();
	int M = X.size();
	
	vector< vector< int > > Graph(N);
	
	for(int i = 0; i < M; i++){
		Graph[X[i]].push_back(Y[i]);
		Graph[Y[i]].push_back(X[i]);
	}
	
	vector<int> A(Q);
	
	if(N <= 3000 && M <= 6000 && Q <= 3000){
	
		
		for(int j = 0; j < Q; j++){
			vector< bool > Human(N, false);
		
			if(S[j] < L[j] || E[j] > R[j]){
				A[j] = 0;
				continue;
			}
		
			queue< int > q;
			q.push(S[j]);
			Human[S[j]] = true;
			
			while(!q.empty()){
				int nodee = q.front();
				q.pop();
				
				for(int neighbours : Graph[nodee]){
					if(Human[neighbours]) continue;
					if(neighbours < L[j]) continue;
					Human[neighbours] = true;
					q.push(neighbours);
				}
			}
			
			q.push(E[j]);
			
			vector< bool > visited(N, false);
			visited[E[j]] = true;
			
			while(!q.empty()){
				int nodee = q.front();
				q.pop();
				
				for(int neigh : Graph[nodee]){
					if(neigh > R[j] || visited[neigh]){
						continue;
					}
					visited[neigh] = true;
					q.push(neigh);
				}
			}
			bool verif = false;
			for(int i = 0; i < N; i++){
				if(Human[i] && visited[i]){
					A[j] = 1;
					verif = true;
					break;
				}
			}
			if(!verif) A[j] = 0;
		}
		
		return A;
	}
	
	int beg = -1;
	
	for(int i = 0; i < N; i++){
		if(Graph[i].size() == 1) beg = i;
	}
	
	dfs(Graph, -1, beg);
	
	node* root = new node{NULL,NULL,0,0};
	Build(root, 1, N);
	
	for(int i = 0; i < Q; i++){
		
		if(S[i] < L[i] || E[i] > R[i]){
			A[i] = 0;
			continue;
		}
		
		if(S[i] < E[i]){
			int indexL = human_right(root, 1, N, S[i], E[i], L[i]);
			int indexR = wolf_left(root, 1,N, S[i], E[i], R[i]);
			if(indexL+1 <= indexR-1 && query(root, 1, N, indexL+1, indexR-1).first > L[i] && query(root, 1, N, indexL+1, indexR-1).second < R[i]){
				A[i] = 1;
			}else{
				A[i] = false;
			}
		}else{
			int indexR = human_left(root, 1, N, S[i], E[i], L[i]);
			int indexL = wolf_right(root, 1,N, S[i], E[i], R[i]);
			if(indexL+1 <= indexR-1 && query(root, 1, N, indexL+1, indexR-1).first > L[i] && query(root, 1, N, indexL+1, indexR-1).second < R[i]){
				A[i] = 1;
			}else{
				A[i] = false;
			}
		}
		
	}
	
	return A;
}

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