Submission #139050

#	Time	Username	Problem	Language	Result	Execution time	Memory
139050		MoNsTeR_CuBe	Werewolf (IOI18_werewolf)	C++17	0 / 100	4006 ms	53496 KiB

werewolf

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

vector< vector< int > > Graph;

int LAST = -1;
int curr = 1;

vector< int > v;

void dfs(int node, int last){
	LAST = node;
	v[curr++] = node;
	for(int a : Graph[node]){
		if(a == last) continue;
		dfs(a, node);
	}
}
////////////////////////////////////////////////
struct node{
	node* l, *r;
	int mini, maxi;
	
	void update(){
		mini = min(l->mini, r->mini);
		maxi = max(l->maxi, r->maxi);
	}
};

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

pair<int, int> Query(node* root, int left, int right, int qLeft, int qRight){
	if(left > qRight || right < qLeft) return {INT_MAX, INT_MIN};
	if(left >= qLeft && right <= qRight){
		return {root->mini, root->maxi};
	}
	int mid = (left+right)/2;
	pair<int, int> p = Query(root->l, left, mid, qLeft, qRight);
	pair<int, int> q = Query(root->r, mid+1, right, qLeft, qRight);
	
	return {min(p.first, q.first), max(p.second, q.second)};
}

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();
	
	Graph.resize(N);
	v.resize(N+1);
	
	for(int i = 0; i < M; i++){
		Graph[X[i]].push_back(Y[i]);
		Graph[Y[i]].push_back(X[i]);
	}
	dfs(0,-1);
	curr = 1;
	dfs(LAST,-1);
	
	vector< int > pos(N);
	
	for(int i = 1; i <= N; i++){
		pos[v[i]] = i;
	}
	
	node *root = new node{NULL,NULL,0,0};
	
	Build(root, 1, N);
	
	vector< int > ans(Q);
	
	for(int i = 0; i < Q; i++){
		if(S[i] < L[i] || E[i] > R[i]){
			ans[i] = 0;
			continue;
		}
		int A = pos[S[i]];
		int B = pos[E[i]];
		if(A < B){
			int left = A;
			int right = B;
			
			while(left < right){
				int mid = (left+right)/2;
				pair<int, int> p = Query(root, 1, N, A, mid);
				
				if(p.first < L[i]){
					right = mid-1;
				}else{
					left = mid;
				}
			}
			
			pair<int, int> p = Query(root, 1, N, left, B);
			
			if(p.second <= R[i]){
				ans[i] = 1;
			}else{
				ans[i] = 0;
			}
		}else{
			int left = B;
			int right = A;
			
			while(left < right){
				int mid = (left+right)/2;
				pair<int, int> p = Query(root, 1, N, B, mid);
				
				if(p.second > R[i]){
					right = mid-1;
				}else{
					left = mid;
				}
			}
			
			pair<int, int> p = Query(root, 1, N, left, A);
			
			if(p.first >= L[i]){
				ans[i] = 1;
			}else{
				ans[i] = 0;
			}
		}
	}
	
	return ans;
}

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