Submission #76689

#	Time	Username	Problem	Language	Result	Execution time	Memory
76689		tincamatei	Werewolf (IOI18_werewolf)	C++14	100 / 100	1270 ms	107128 KiB

werewolf

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

const int MAX_N = 200000;
const int MAX_Q = 200000;

std::vector<int> graph[MAX_N], graph1[MAX_N], graph2[MAX_N];
std::vector<int> queryId[MAX_N];
int par1[20][MAX_N+1], par2[20][MAX_N+1];
int entryT[MAX_N], exitT[MAX_N];
int top, eulertour[1+MAX_N], poz[1+MAX_N];
int subarb[1+MAX_N];
int aib[1+MAX_N];
int sef1[MAX_N], sef2[MAX_N];
bool bl1[MAX_N], bl2[MAX_N];

static inline int lsb(int x) {
	return x & (-x);
}

void updateAib(int poz, int val) {
	while(poz <= MAX_N) {
		aib[poz] += val;
		poz += lsb(poz);
	}
}

int queryAib(int poz) {
	int rez = 0;
	while(poz > 0) {
		rez += aib[poz];
		poz -= lsb(poz);
	}
	return rez;
}

struct Query {
	int a, b, rez;
} query[MAX_Q];

void calcBinaryLifting(int n) {
	for(int l = 1; l < 20; ++l)
		for(int i = 0; i < n; ++i) {
			par1[l][i] = par1[l - 1][par1[l - 1][i]];
			par2[l][i] = par2[l - 1][par2[l - 1][i]];
		}
}

int searchSmaller(int src, int val) {
	for(int l = 19; l >= 0; --l) {
		int jump = par1[l][src];
		if(jump != MAX_N && jump <= val)
			src = jump;
	}
	return src;
}

int searchGreater(int src, int val) {
	for(int l = 19; l >= 0; --l) {
		int jump = par2[l][src];
		if(jump != MAX_N && jump >= val)
			src = jump;
	}
	return src;
}

void dfs(int nod) {
	entryT[nod] = top + 1;
	for(auto it: graph1[nod])
		dfs(it);
	poz[nod] = ++top;
	eulertour[top] = nod;
	exitT[nod] = top;
}

void dfs2(int nod) {
	subarb[nod] = 1;
	for(auto it: graph2[nod]) {
		dfs2(it);
		subarb[nod] += subarb[it];
	}
}

void dfs3(int nod, int val = 0) {
	int heavySon = -1, heavySize = 0;
	for(auto it: graph2[nod])
		if(subarb[it] > heavySize) {
			heavySize = subarb[it];
			heavySon = it;
		}
	
	if(val == 0) {
		for(auto it: graph2[nod])
			if(it != heavySon) {
				dfs3(it, val);
				dfs3(it, -1);
			}
		if(heavySon != -1)
			dfs3(heavySon, 0);
		for(auto it: graph2[nod])
			if(it != heavySon)
				dfs3(it, 1);
		
		updateAib(poz[nod], 1);
		
		for(auto it: queryId[nod]) {
			if(queryAib(exitT[query[it].a]) - queryAib(entryT[query[it].a] - 1) > 0)
				query[it].rez = 1;
		}
	} else {
		for(auto it: graph2[nod])
			dfs3(it, val);
		updateAib(poz[nod], val);
	}
}

int myfind(int x, int *sef) {
	if(x == sef[x])
		return x;
	else {
		sef[x] = myfind(sef[x], sef);
		return sef[x];
	}
}

void myunion(int a, int b, int *sef, bool doMin = true) {
	int sa = myfind(a, sef), sb = myfind(b, sef);

	if((doMin && sa < sb) || (!doMin && sa > sb))
		sef[sb] = sa;
	else
		sef[sa] = sb;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int Q = S.size(), M = X.size();
	std::vector<int> A(Q);
	
	for(int i = 0; i < M; ++i) {
		graph[X[i]].push_back(Y[i]);
		graph[Y[i]].push_back(X[i]);
	}
	
	for(int l = 0; l < 20; ++l)
		par1[l][MAX_N] = par2[l][MAX_N] = MAX_N;
	
	for(int i = 0; i < N; ++i)
		sef1[i] = sef2[i] = i;

	for(int i = 0; i < N; ++i) {
		par1[0][i] = par2[0][i] = MAX_N;
		for(auto it: graph[i])
			if(it < i && myfind(i, sef1) != myfind(it, sef1)) {
				par1[0][myfind(it, sef1)] = i;
				graph1[i].push_back(myfind(it, sef1));
				myunion(i, it, sef1, false);
			}
	}
	
	for(int i = N - 1; i >= 0; --i) 
		for(auto it: graph[i])
			if(it > i && myfind(i, sef2) != myfind(it, sef2)) {
				par2[0][myfind(it, sef2)] = i;
				graph2[i].push_back(myfind(it, sef2));
				myunion(i, it, sef2);
			}
	
	calcBinaryLifting(N);
	dfs(N - 1);
	dfs2(0);
	for(int i = 0; i < Q; ++i) {
		query[i].a = searchSmaller(E[i], R[i]);
		query[i].b = searchGreater(S[i], L[i]);
		queryId[query[i].b].push_back(i);
	}

	dfs3(0);

	for(int i = 0; i < Q; ++i)
		A[i] = query[i].rez;
	return A;
}

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