Submission #114108

#	Time	Username	Problem	Language	Result	Execution time	Memory
114108		antimirage	Werewolf (IOI18_werewolf)	C++14	0 / 100	4074 ms	524288 KiB

werewolf

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

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

vector < vector <int> > g;

const int N = 2e5 + 5;

int n, m, beg, ind[N], a[N], t[2][N];

void dfs (int v, int p = -1)
{
	beg = v;
	for (auto to : g[v])
	{
		if (to == p) continue;
		dfs(to, v);
	}
}
void Dfs (int v, int i, int p = -1)
{
	ind[v] = i;
	a[i] = v;
	
	for (auto to : g[v])
	{
		if (to == p) continue;
		Dfs(to, i + 1, v);
	}	
}
void build (int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
		t[0][v] = t[1][v] = a[tl];
	else{
		int tm = (tl + tr) >> 1;
		build( v + v, tl, tm );
		build( v + v + 1, tm + 1, tr );
	
		t[0][v] = min( t[0][v + v], t[0][v + v + 1] );
		t[1][v] = max( t[1][v + v], t[1][v + v + 1] );
	}
}
int get (int l, int r, int typ, int v = 1, int tl = 1, int tr = n)
{
	if (l > tr || tl > r)
		return typ == 0 ? 1e9 : -1e9;
		
	if (l <= tl && tr <= r)
		return t[typ][v];
		
	int tm = (tl + tr) >> 1;
	
	if (typ == 0)
		return min( get(l, r, typ, v + v, tl, tm), get(l, r, typ, v + v + 1, tm + 1, tr) );
		
	return max( get(l, r, typ, v + v, tl, tm), get(l, r, typ, v + v + 1, tm + 1, tr) );
}
pair <int, int> calc (int pos, int l, int r)
{
	pair <int, int> res;

	int L = 0, R = n;
	
	while (R - L > 1)
	{
		int md = (L + R) >> 1;
		if ( pos - md >= 1 && get( pos - md, pos, 0 ) >= l && get( pos - md, pos, 1 ) <= r )
			L = md;
		else
			R = md;
	}
	res.fr = pos - L;
	
	L = 0, R = n;
	
	while (R - L > 1)
	{
		int md = (L + R) >> 1;
		if ( pos + md <= n && get( pos, pos + md, 0 ) >= l && get( pos, pos + md, 1 ) <= r )
			L = md;
		else
			R = md;
	}
	res.sc = pos + L;
	
	return res;
}

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;
	m = x.size();
	g.resize(n + 1);
	
	for (int i = 0; i < m; i++)
		g[ x[i] ].pb( y[i] ),
		g[ y[i] ].pb( x[i] );
	
	
	dfs(0);
	
	Dfs(beg, 1);
	
	build ();
	
	int q = s.size();
	
	vector <int> ans;
	
	for (int i = 0; i < q; i++)
	{
		if ( s[i] < l[i] || e[i] > r[i] )
		{
			ans.pb(0);
			continue;
		}
		pair <int, int> a = calc( ind[s[i]], l[i], n - 1 );
		pair <int, int> b = calc( ind[e[i]], 0, r[i] );
		
		if (a.fr > b.sc || b.fr > a.sc)
			ans.pb(0);
		else
			ans.pb(1);
	}
	return ans;
}
/**
6 5 0
2 5
5 6
0 1
1 3
3 4
**/

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