Submission #109407

#	Time	Username	Problem	Language	Result	Execution time	Memory
109407		SirCeness	Werewolf (IOI18_werewolf)	C++14	0 / 100	645 ms	525312 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

#define pb push_back 

#define INF 1000000009

using namespace std;

list<int> adj[200005];
int arr[200005];
int st[200005*4][2];

int n;

void carr(int i, int node, int anc){
	arr[i] = node;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (*it == anc) continue;
		carr(i+1, *it, node);
	}
}

void stc(int node, int l, int r, int mode){
	if (l == r) st[node][mode] = arr[l];
	else {
		int mid = (l+r)/2;
		stc(node*2, l, mid, mode);
		stc(node*2+1, mid+1, r, mode);
		if (mode == 0){
			st[node][mode] = min(st[node*2][mode], st[node*2+1][mode]);
		} else {
			st[node][mode] = max(st[node*2][mode], st[node*2+1][mode]);
		}
	}
}

int stq(int node, int l, int r, int mode, int sl, int sr){
	if (sl <= l && r <= sr){
		return st[node][mode];
	} else if (r < sl || l < sr){
		if (mode == 0) return INF;
		else return -1;
	} else {
		int mid = (l+r)/2;
		if (mode == 0){
			return min(stq(node*2, l, mid, mode, sl, sr), stq(node*2+1, mid+1, r, mode, sl, sr));
		} else {
			return max(stq(node*2, l, mid, mode, sl, sr), stq(node*2+1, mid+1, r, mode, sl, sr));
		}
	}
}

pair<int, int> check(int s, int m, int t, int l, int r){
	pair<int, int> ans = make_pair(0, 0);
	int minn = stq(1, 0, n-1, 0, s, m);
	if (minn >= l) ans.first = 1;
	int maxx = stq(1, 0, n-1, 1, m, t);
	if (maxx <= r) ans.second = 1;
	return ans;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	
	n = N;
	for (int i = 0; i < n; i++){
		adj[X[i]].pb(Y[i]);
	}
	
	int nodes = -1;
	for (int i = 0; i < n; i++){
		if (adj[i].size() == 1){
			nodes = i;
			break;
		}
	}
	
	carr(0, nodes, -1);
	stc(1, 0, n-1, 0);
	stc(1, 0, n-1, 1);
	
	int Q = S.size();
	vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		int l = min(S[i], E[i]);
		int r = max(S[i], E[i]);
		int s = l;
		int t = r;
		while (l < r){
			int mid = (l+r)/2;
			pair<int, int> ans = check(s, mid, t, L[i], R[i]);
			if (ans.first == 0 && ans.second == 0){
				break;
			} else if (ans.first == 0 && ans.second == 1){
				r = mid-1;
			} else if (ans.first == 1 && ans.second == 0){
				l = mid+1;
			} else {
				break;
			}
		}
		pair<int, int> ans = check(s, l, t, L[i], R[i]);
		A[i] = (ans.first == 1 && ans.second == 1);
	}
	return A;
}

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