Submission #773189

#	Time	Username	Problem	Language	Result	Execution time	Memory
773189		amunduzbaev	Werewolf (IOI18_werewolf)	C++17	34 / 100	521 ms	97668 KiB

werewolf

#include "werewolf.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll

const int N = 2e5 + 5;

struct ST{
	int tree[N << 2];
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r){
			return tree[x];
		}
		
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree;

const int M = 18;
vector<int> qwe[N], edges[2][N];
int tin[2][N], tout[2][N];
int par[2][N][M];

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
	int m = x.size(), q = s.size();
	for(int i=0;i<m;i++){
		qwe[x[i]].push_back(y[i]);
		qwe[y[i]].push_back(x[i]);
	}
	
	{ // building trees
		vector<int> par(n), sz(n, 1), root(n);
		iota(par.begin(), par.end(), 0);
		iota(root.begin(), root.end(), 0);
		
		function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
		auto merge = [&](int a, int b, int r){
			a = f(a), b = f(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			par[b] = a;
			root[a] = r;
			sz[a] += sz[b];
		};
		
		for(int i=n - 1;~i;i--){
			for(auto x : qwe[i]){
				if(x > i && root[f(x)] != i){
					edges[0][i].push_back(root[f(x)]);
					merge(x, i, i);
				}
			}
		}
		
		iota(par.begin(), par.end(), 0);
		iota(root.begin(), root.end(), 0);
		fill(sz.begin(), sz.end(), 1);
		
		for(int i=0;i<n;i++){
			for(auto x : qwe[i]){
				if(x < i && root[f(x)] != i){
					edges[1][i].push_back(root[f(x)]);
					merge(x, i, i);
				}
			}
		}
	}
	
	//~ for(int t=0;t<2;t++){
		//~ for(int i=0;i<n;i++){
			//~ for(auto x : edges[t][i]){
				//~ cout<<t<<" "<<i<<" "<<x<<"\n";
			//~ }
		//~ }
		
		//~ cout<<"\n";
	//~ }
	
	ar<int, 2> root = {0, n - 1};

	for(int t=0;t<2;t++){
		int t_ = 0;
		function<void(int)> dfs = [&](int u){
			for(int j=1;j<M;j++){
				par[t][u][j] = par[t][par[t][u][j - 1]][j - 1];
			}
			tin[t][u] = ++t_;
			for(auto x : edges[t][u]){
				par[t][x][0] = u;
				dfs(x);
			}
			tout[t][u] = t_;
		};
		
		par[t][root[t]][0] = root[t];
		dfs(root[t]);
	}
	
	vector<ar<int, 2>> ver(n);
	
	auto get = [&](int t, int u, int l, int r){
		for(int j=M - 1;~j;j--){
			if(l <= par[t][u][j] && par[t][u][j] <= r){
				u = par[t][u][j];
			}
		}
		
		return u;
	};
	
	for(int i=0;i<q;i++){
		ver[i][0] = get(0, s[i], l[i], n);
		ver[i][1] = get(1, e[i], 0, r[i]);
	}
	
	vector<int> p(q);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return tout[0][ver[i][0]] < tout[0][ver[j][0]];
	});
	
	vector<int> tot(n);
	iota(tot.begin(), tot.end(), 0);
	sort(tot.begin(), tot.end(), [&](int i, int j){
		return tout[0][i] < tout[0][j];
	});
	
	vector<int> res(q);
	int j = 0;
	for(auto i : p){
		while(j < n && tin[0][tot[j]] <= tout[0][ver[i][0]]){
			tree.set(tin[1][tot[j]], tin[0][tot[j]]);
			j++;
		}
		
		if(tree.get(tin[1][ver[i][1]], tout[1][ver[i][1]]) >= tin[0][ver[i][0]]){
			res[i] = 1;
		}
	}
	
	return res;
}

/*

6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4

5 4 4
4 1
1 0
0 3
3 2
4 0 1 1 
4 3 1 3
2 0 1 1
3 1 3 3

*/

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