Submission #139947

#	Time	Username	Problem	Language	Result	Execution time	Memory
139947		mosesmayer	Werewolf (IOI18_werewolf)	C++17	34 / 100	624 ms	61960 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef vector<int> vi;

const int MX = 2e5;
int spt_mn[19][MX + 5];
int spt_mx[19][MX + 5];
int vals[MX + 5];
int n, m;
vi adj[MX + 5];
int flat[MX + 5], in[MX + 5], lg[MX + 5];

void dfs(int u, int prv = 0){
	static int tme = 0;
	in[u] = ++tme;
	flat[tme] = u;
	vals[tme] = u;
	for (int nx : adj[u]){
		if (nx != prv) dfs(nx, u);
	}
}
void computeSparseTable(){
	int st = 1;
	for (; adj[st].size() != 1; st++);
	dfs(st);
	lg[1] = 0;
	for (int j = 1; j <= n; j++){
		spt_mn[0][j] = spt_mx[0][j] = vals[j];
		if (j > 1) lg[j] = lg[j >> 1] + 1;
	}
	for (int i = 1; i <= 18; i++){
		for (int j = 1; j + (1 << (i-1)) <= n; j++){
			spt_mn[i][j] = min(spt_mn[i-1][j], spt_mn[i-1][j + (1 << (i-1))]);
			spt_mx[i][j] = max(spt_mx[i-1][j], spt_mx[i-1][j + (1 << (i-1))]);
		}
	}
}
int get_mn(int l, int r){
	assert(l <= r);
	int L = lg[r - l + 1];
	return min(spt_mn[L][l], spt_mn[L][r - (1<<L) + 1]);
}
int get_mx(int l, int r){
	assert(l <= r);
	int L = lg[r - l + 1];
	return max(spt_mx[L][l], spt_mx[L][r - (1<<L) + 1]);
}

int query(int s, int e, int l, int r){
	if (in[s] <= in[e]){
		int lo = in[s], hi = in[e], md, human_bnd = in[s] - 1, werewolf_bnd = in[e] + 1;;
		while (lo <= hi){
			md = (lo + hi) >> 1;
			if (get_mn(in[s], md) >= l) human_bnd = md, lo = md + 1;
			else hi = md - 1;
		}
		lo = in[s], hi = in[e];
		while (lo <= hi){
			md = (lo + hi) >> 1;
			if (get_mx(md, in[e]) <= r) werewolf_bnd = md, hi = md - 1;
			else lo = md + 1;
		}
		return human_bnd >= werewolf_bnd ? 1 : 0;
	} else {
		int lo = in[e], hi = in[s], md, human_bnd = in[s] + 1, werewolf_bnd = in[e] - 1;;
		while (lo <= hi){
			md = (lo + hi) >> 1;
			if (get_mn(md, in[s]) >= l) human_bnd = md, hi = md - 1;
			else lo = md + 1;
		}
		lo = in[e], hi = in[s];
		while (lo <= hi){
			md = (lo + hi) >> 1;
			if (get_mx(in[e], md) <= r) werewolf_bnd = md, lo = md + 1;
			else hi = md - 1;
		}
		return human_bnd <= werewolf_bnd ? 1 : 0;
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n = N; m = X.size();
	for (int i = 0; i < m; i++){
		adj[X[i]].eb(Y[i]);
		adj[Y[i]].eb(X[i]);
	}
	computeSparseTable();
	int Q = S.size();
	std::vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		A[i] = query(S[i], E[i], L[i], R[i]);
	}
	return A;
}

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