Submission #1196432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196432		Muhammet	Werewolf (IOI18_werewolf)	C++20	100 / 100	1167 ms	169028 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
// #include "grader.cpp"

using namespace std;

#define SZ(s) (int)s.size()

const int N = 2e5 + 5;

vector <int> v[N], d[2][N], p[2][N], pr, vec, st[N*4];

int in[2][N], out[2][N], tim;

int fnd(int x) {
	if(pr[x] == x) return x;
	return pr[x] = fnd(pr[x]);
}

void dfs(int x, int t) {
	vec.push_back(x);
	in[t][x] = ++tim - 1;
	for(auto i : d[t][x]) {
		dfs(i, t);
	}
	out[t][x] = tim - 1;
}

vector <int> a, b;

void bld(int nd, int l, int r) {
	if(l == r) {
		st[nd].push_back(vec[l]);
		return;
	}
	int md = (l + r) / 2;
	bld(nd*2, l, md), bld(nd*2+1, md+1, r);
	a = st[nd*2], b = st[nd*2+1];
	reverse(a.begin(), a.end()), reverse(b.begin(), b.end());
	while(SZ(a) or SZ(b)) {
		if((SZ(a)) and (!SZ(b) or a.back() <= b.back())) {
			st[nd].push_back(a.back());
			a.pop_back();
			continue;
		}
		st[nd].push_back(b.back());
		b.pop_back();
	}
	return;
}

bool tr;

void fnd(int nd, int l, int r, int x, int y, int x1, int y1) {
	if(tr) return;
	if(l > y or r < x or st[nd].back() < x1) return;
	if(l >= x and r <= y) {
		if(*lower_bound(st[nd].begin(), st[nd].end(), x1) <= y1) tr = 1;
		return;
	}
	int md = (l + r) / 2;
	fnd(nd*2, l, md, x, y, x1, y1), fnd(nd*2+1, md+1, r, x, y, x1, y1);
}

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 = SZ(x), q = SZ(S);
	for(int i = 0; i < m; i++) {
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	vector <vector <vector <int>>> sp(2, vector <vector <int>> (n, vector <int> (25, 0)));
	pr.resize(n);
	for(int i = 0; i < n; i++) {
		pr[i] = i, sp[0][i][0] = i;
	}
	for(int i = n-1; i >= 0; i--) {
		for(auto j : v[i]) {
			if(j < i) continue;
			int k = fnd(j);
			if(k == i) continue;
			pr[k] = i;
			sp[0][k][0] = i;
			d[0][i].push_back(k);
		}
	}
	for(int i = 0; i < n; i++) {
		pr[i] = i, sp[1][i][0] = i;
	}
	for(int i = 0; i < n; i++) {
		for(auto j : v[i]) {
			if(i < j) continue;
			int k = fnd(j);
			if(k == i) continue;
			pr[k] = i;
			sp[1][k][0] = i;
			d[1][i].push_back(k);
		}
	}
	for(int j = 1; j < 25; j++) {
		for(int i = 0; i < n; i++) {
			sp[0][i][j] = sp[0][sp[0][i][j-1]][j-1];
			sp[1][i][j] = sp[1][sp[1][i][j-1]][j-1];
		}
	}
	dfs(0, 0);
	vec.clear(), tim = 0;
	dfs(n-1, 1);
	for(int i = 0; i < n; i++) {
		vec[i] = in[0][vec[i]];
	}
	bld(1, 0, n-1);
	vector <int> ans;
	for(int i1 = 0; i1 < q; i1++) {
		int s = S[i1], e = E[i1], l = L[i1], r = R[i1];
		for(int i = 24; i >= 0; i--) {
			if(sp[0][s][i] >= l) s = sp[0][s][i];
			if(sp[1][e][i] <= r) e = sp[1][e][i];
		}
		tr = 0;
		fnd(1, 0, n-1, in[1][e], out[1][e], in[0][s], out[0][s]);
		ans.push_back(tr);
	}
	return ans;
}

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