Submission #138519

#	Time	Username	Problem	Language	Result	Execution time	Memory
138519		Mahdi_Jfri	Werewolf (IOI18_werewolf)	C++14	100 / 100	1212 ms	117080 KiB

werewolf

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;
const int maxb = 20;

vector<int> adj[maxn] , tree[2][maxn] , query[maxn];

int px[maxn] , par[2][maxn][maxb] , st[2][maxn] , ft[2][maxn] , id , rst[2][maxn];

int l1[maxn] , r1[maxn] , l2[maxn] , r2[maxn];

int root(int v)
{
	return px[v] < 0? v : px[v] = root(px[v]);
}

void dfs(int v , int b , int p = -1)
{
	if(p == -1)
	{
		for(int i = 0; i < maxb; i++)
			par[b][v][i] = v;
		id = -1;
	}

	st[b][v] = ++id;
	rst[b][id] = v;
	for(auto u : tree[b][v])
	{
		par[b][u][0] = v;
		for(int i = 1; i < maxb; i++)
			par[b][u][i] = par[b][par[b][u][i - 1]][i - 1];

		dfs(u , b , v);
	}

	ft[b][v] = id;
}

int n , mx[maxn * 4];

void upd(int p , int val , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		mx[v] = val;
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		upd(p , val , s , m , 2 * v);
	else
		upd(p , val , m , e , 2 * v + 1);

	mx[v] = max(mx[2 * v] , mx[2 * v + 1]);
}

int get(int l , int r , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
		return mx[v];
	if(r <= s || e <= l)
		return -1;

	int m = (s + e) / 2;

	return max(get(l , r , s , m , 2 * v) , get(l , r , m , e , 2 * v + 1));
}

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 < (int)X.size(); i++)
	{
		int a = X[i] , b = Y[i];

		adj[a].pb(b);
		adj[b].pb(a);
	}

	memset(px , -1 , sizeof px);
	for(int v = 0; v < n; v++)
		for(auto u : adj[v])
			if(u < v)
			{
				u = root(u);
				if(u != v)
					tree[0][v].pb(u) , px[u] = v;
			}

	memset(px , -1 , sizeof px);
	for(int v = n - 1; v >= 0; v--)
		for(auto u : adj[v])
			if(u > v)
			{
				u = root(u);
				if(u != v)
					tree[1][v].pb(u) , px[u] = v;
			}

	dfs(n - 1 , 0) , dfs(0 , 1);

	int q = S.size();
	for(int i = 0; i < q; i++)
	{
		int s = S[i] , e = E[i];

		for(int j = maxb - 1; j >= 0; j--)
			if(par[0][e][j] <= R[i])
				e = par[0][e][j];

		for(int j = maxb - 1; j >= 0; j--)
			if(par[1][s][j] >= L[i])
				s = par[1][s][j];

		l1[i] = st[0][e] , r1[i] = ft[0][e];
		l2[i] = st[1][s] , r2[i] = ft[1][s];
		query[r1[i]].pb(i);
	}

	memset(mx , -1 , sizeof mx);

	vector<int> ans(q);
	for(int i = 0; i < n; i++)
	{
		int v = rst[0][i];
		upd(st[1][v] , i);

		for(auto ind : query[i])
			ans[ind] = get(l2[ind] , r2[ind] + 1) >= l1[ind];
	}

	return ans;
}

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