Submission #114113

#	Time	Username	Problem	Language	Result	Execution time	Memory
114113		antimirage	늑대인간 (IOI18_werewolf)	C++14	34 / 100	968 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][20][N], lg[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 ()
{
	lg[1] = 0;
	
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i / 2] + 1;
		
	for (int i = 1; i <= n; i++){
		t[0][0][i] = a[i], t[1][0][i] = a[i];
	}
		
	for (int i = 1; i < 20; i++)
	{
		for (int j = (1 << i); j <= n; j++)
			t[0][i][j] = min( t[0][i - 1][j], t[0][i - 1][j - (1 << (i - 1) ) ] ),
			t[1][i][j] = max( t[1][i - 1][j], t[1][i - 1][j - (1 << (i - 1) ) ] );
	}
}
inline int get (int l, int r, int typ)
{
	int pw = lg[r - l];
	
	if (typ == 0){
		return min( t[0][pw][r], t[0][pw][l + (1 << pw) - 1] );
	}
	else{
		return max( t[1][pw][r], t[1][pw][l + (1 << pw) - 1] );
	}
}
inline 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: 34 / 34
• Subtask 4: 0 / 51