Submission #606937

#	Time	Username	Problem	Language	Result	Execution time	Memory
606937		amunduzbaev	Werewolf (IOI18_werewolf)	C++17	0 / 100	226 ms	60224 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;

const int N = 2e5 + 5;

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

vector<int> edges[2][N];
int c[N], lift[2][N][20];
int tin[2][N], tout[2][N], t_;
int par[N];

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(), t;
	function<int(int)> f = [&](int x){ return (par[x] == x ? x : par[x] = f(par[x])); };
	auto merge = [&](int a, int b){
		a = f(a), b = f(b);
		if(a == b){
			return;
		}
		
		if(b > a && !t) swap(a, b);
		if(a > b && t) swap(a, b);
		edges[t][a].push_back(b);
		par[b] = a;
	};
	
	vector<ar<int, 2>> e;
	for(int i=0;i<m;i++){
		e.push_back({max(X[i], Y[i]), i});
	} sort(e.begin(), e.end());
	iota(par, par + n, 0);
	t = 0;
	for(auto [c, i] : e){
		merge(X[i], Y[i]);
	} int r1 = f(0); 
	
	e.clear();
	for(int i=0;i<m;i++){
		e.push_back({min(X[i], Y[i]), i});
	} sort(e.rbegin(), e.rend());
	iota(par, par + n, 0);
	t = 1;
	for(auto [c, i] : e){
		merge(X[i], Y[i]);
	} int r2 = f(0);
	
	
	//~ for(int i=0;i<m;i++){
		//~ cout<<X[i] + n<<" "<<Y[i] + n<<"\n";
	//~ }
	
	//~ for(int i=0;i<n;i++){
		//~ for(auto x : edges[0][i]) cout<<i<<" "<<x<<"\n";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ for(auto x : edges[1][i]) cout<<i<<" "<<x<<"\n";
	//~ } cout<<"\n";
	
	//~ cout<<r1<<" "<<r2<<"\n";
	
	vector<int> V;
	function<void(int)> dfs = [&](int u){
		tin[t][u] = ++t_;
		if(t) V.push_back(u);
		for(int j=1;j<20;j++){
			lift[t][u][j] = lift[t][lift[t][u][j-1]][j-1];
		}
		
		for(auto x : edges[t][u]){
			lift[t][x][0] = u;
			dfs(x);
		}
		tout[t][u] = t_;
	};
	assert(false);
	t = 0; t_ = 0;
	lift[t][r1][0] = r1;
	dfs(r1);
	
	t = 1; t_ = 0;
	lift[t][r2][0] = r2;
	dfs(r2);
	
	assert((int)V.size() == n);
	
	int q = S.size();
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	for(int i=0;i<q;i++){
		int v = S[i];
		for(int j=19;~j;j--){
			if(lift[1][v][j] >= L[i]) v = lift[1][v][j];
		}
		S[i] = v;
		
		v = E[i];
		for(int j=19;~j;j--){
			if(lift[0][v][j] <= R[i]) v = lift[0][v][j];
		}
		E[i] = v;
	}
	//~ for(int i=0;i<q;i++) cout<<S[i]<<" "<<E[i]<<"\n";
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return tout[1][S[p[i]]] < tout[1][S[p[j]]];
	});
	
	vector<int> res(q);
	int j = 0;
	for(auto i : p){ int x = S[i];
		while(j < n && j + 1 <= tout[1][x]){
			tree.set(tin[0][V[j]], tin[1][V[j]]);
			j++;
		}
		
		res[i] = (tree.get(tin[0][E[i]], tout[0][E[i]]) >= tin[1][x]);
	}
	
	return res;
}

/*

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

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

*/

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