Submission #125345

#	Time	Username	Problem	Language	Result	Execution time	Memory
125345		someone_aa	Werewolf (IOI18_werewolf)	C++17	100 / 100	1352 ms	129400 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;

int n, m, q;
vector<int>g[maxn];

vector<pair<int, int> > queries[maxn];
int result[maxn];

class dsu {
public:
	int usize[maxn], uparent[maxn], parent[maxn];
	vector<int>tree_g[maxn];

	int sparse[maxn][20], euler[maxn], intime[maxn];
	int sbtsize[maxn];
	int br;

	void init() {
		br = 1;
		for(int i=0;i<=n;i++) {
			usize[i] = 1;
			uparent[i] = i;
			parent[i] = i;
		}
		memset(sparse,-1,sizeof(sparse));
	}
	int ufind(int x) {
		while(x != uparent[x]) x = uparent[x];
		return x;
	}
	void add_edge(int i, int j) {
		tree_g[i].pb(j);
		tree_g[j].pb(i);

	}
	void unite(int x, int y, int d) {
		x = ufind(x);
		y = ufind(y);	

		if(x == y) return;

		add_edge(parent[x], parent[y]);


		//cout<<"Mering "<<x<<" "<<y<<" -> "<<parent[y]<<"\n";

		if(usize[x] > usize[y]) {
			uparent[y] = x;
			parent[x] = d;
			usize[x] += usize[y];
		}
		else {
			uparent[x] = y;
			parent[y] = d;
			usize[y] += usize[x];
		}
	}
	void dfs(int node, int p = -1) {
		//cout<<node<<"\n";

		sparse[node][0] = p;
		for(int i=1;i<20;i++) {
			if(sparse[node][i-1] != -1) {
				sparse[node][i] = sparse[sparse[node][i-1]][i-1];
			}
		}

		euler[br] = node;
		intime[node] = br;
		br++;

		sbtsize[node] = 1;

		for(int i:tree_g[node]) {
			if(i != p) {
				dfs(i, node);
				sbtsize[node] += sbtsize[i];
			}
		}
	}
}x, y;

int tree[4*maxn];

void update(int x, int val, int li = 0, int ri = n, int index=1) {
	if(li == ri) tree[index] += val;
	else {
		int mid = (li + ri) / 2;
		if(x <= mid) update(x, val, li, mid, 2*index);
		else update(x, val, mid+1, ri, 2*index+1);
		tree[index] = tree[2*index] + tree[2*index+1];
	}
}

int query(int ql, int qr, int li=0, int ri = n, int index = 1) {
	if(li > qr || ri < ql) return 0;
	else if(li >= ql && ri <= qr) return tree[index];
	else {
		int mid = (li + ri) / 2;
		return query(ql, qr, li, mid, 2*index) + query(ql, qr, mid+1, ri, 2*index+1);
	}
}

void dfs_x(int node = n - 1, int parent = -1, bool keep = true) {
	int big_size = -1;
	int big_ind = -1;

	for(int i:x.tree_g[node]) {
		if(i != parent) {
			if(x.sbtsize[i] > big_size) {
				big_size = x.sbtsize[i];
				big_ind = i;
			}
		}
	}


	for(int i:x.tree_g[node]) {
		if(i != parent && i != big_ind) {
			dfs_x(i, node, false);
		}
	}

	if(big_ind != -1) {
		dfs_x(big_ind, node, true);
	}

	for(int i:x.tree_g[node]){
		if(i == parent || i == big_ind) continue;
		for(int j=x.intime[i];j<x.intime[i] + x.sbtsize[i];j++) {
			update(y.intime[x.euler[j]], 1);
		}
	}

	update(y.intime[node], 1);

	for(auto i:queries[node]) {
		//cout<<"Find intersection between "<<node<<" and "<<i.first<<"\n";
		result[i.second] = query(y.intime[i.first], y.intime[i.first] + y.sbtsize[i.first] - 1);
	}

	if(!keep) {
		for(int i=x.intime[node];i<x.intime[node] + x.sbtsize[node];i++) {
			update(y.intime[x.euler[i]], -1);
		}
	}
}

void precalculate(vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	x.init();
 	for(int i=0;i<n;i++) {
 		for(int j:g[i]) {
 			if(i > j) {
 				x.unite(i, j, x.parent[x.ufind(i)]);
 			}
 		}
 	}
 	y.init();
 	for(int i=n-1;i>=0;i--) {
 		for(int j:g[i]) {
 			if(i < j) {
 				y.unite(i, j, y.parent[y.ufind(i)]);
 			}
 		}
 	}

 	x.dfs(n-1);
 	//cout<<"--->\n";
 	y.dfs(0);
 	//cout<<"Done printing trees\n";

 	for(int i=0;i<q;i++) {
 		int curr = S[i];
 		for(int j=19;j>=0;j--) {
 			if(y.sparse[curr][j] >= L[i]) curr = y.sparse[curr][j];
 		}
 		//cout<<"Query: "<<i<<"\n";
 		//cout<<S[i]<<" - "<<curr<<"\n";

 		int curr_2 = E[i];
 		for(int j=19;j>=0;j--) {
 			//cout<<j<<": "<<curr_2<<", "<<x.sparse[curr_2][j]<<"\n";
 			if(x.sparse[curr_2][j] <= R[i] && x.sparse[curr_2][j] != -1) curr_2 = x.sparse[curr_2][j];
 		}

 		//cout<<E[i]<<" - "<<curr_2<<"\n";

 		queries[curr_2].pb(mp(curr, i));
 	}

 	dfs_x();
}


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();
 	q = S.size();

 	for(int i=0;i<m;i++) {
 		g[X[i]].pb(Y[i]);
 		g[Y[i]].pb(X[i]);
 	}

 	precalculate(S,E,L,R);

 	vector<int>v(q, 0);
 	for(int i=0;i<q;i++) {
 		v[i] = result[i];
 		if(v[i] > 0) v[i] = 1;
 	}
 	return v;
}

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