Submission #619489

#	Time	Username	Problem	Language	Result	Execution time	Memory
619489		Vanilla	Werewolf (IOI18_werewolf)	C++17	100 / 100	835 ms	124020 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
const int lg = 20;
vector <int> ad [maxn];
vector <int> reach [2][maxn];
int dsu [maxn];
int bit [maxn * 2 + 200];
int up [2][maxn][lg];
int in [2][maxn];
int val [2][maxn];
int sz [2][maxn];
int ps = 2;

int dad (int x) {
	return dsu[x] = (x == dsu[x] ? x: dad(dsu[x]));
}

void dfs (int t, int u) {
	in[t][u] = ++ps, sz[t][u] = 1;
	for (int i = 1; i < lg; i++){
		up[t][u][i] = up[t][up[t][u][i-1]][i-1];
	}
	for (int v: reach[t][u]) {
		up[t][v][0] = u;
		dfs(t, v);
		sz[t][u]+=sz[t][v];
	}
}

void add (int x, int y) {
	for (; x < maxn * 2 + 20; x+=x & -x) bit[x]+=y;
}

int query (int x) {
	int rs = 0;
	for (; x; x-=x & -x) rs+=bit[x];
	return rs;
}

struct event {
	int type; // 1 -> start, 2 -> point, 3 -> end
	int x; // OX
	int l; // OY
	int r; // OY		
	int idx;

	inline bool operator < (const event& oth) const {
		if (x == oth.x) return type < oth.type;
		return x < oth.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) {
	int M = X.size(), Q = L.size();
	vector <int> rs (Q);
	for (int i = 0; i < M; i++){
		ad[X[i]].push_back(Y[i]);
		ad[Y[i]].push_back(X[i]);
	}
	iota (dsu, dsu + maxn, 0);
	for (int i = 0; i < N; i++){
		for (int j: ad[i]) {
			if (j > i) continue;
			if (dad(j) != i) {
				reach[0][i].push_back(dad(j));
				dsu[dad(j)] = i;
			}
		}
	}
	iota (dsu, dsu + maxn, 0);
	for (int i = N - 1; i >= 0; i--) {
		for (int j: ad[i]) {
			if (j < i) continue;
			if (dad(j) != i) {
				reach[1][i].push_back(dad(j));
				dsu[dad(j)] = i;
			}
		}
	}
	up[0][N-1][0] = N-1;
	up[1][0][0] = 0;
	dfs(0, N - 1);
	ps = 2;
	dfs(1, 0);
	for (int i = 0; i < Q; i++){
		for (int j = lg - 1; j >= 0; j--){
			if (up[1][S[i]][j] >= L[i]) S[i] = up[1][S[i]][j];
			if (up[0][E[i]][j] <= R[i]) E[i] = up[0][E[i]][j];
		}
	}
	vector <event> ev;
	for (int i = 0; i < N; i++){
		ev.push_back({2, in[1][i], in[0][i], in[0][i], i});
	}
	for (int i = 0; i < Q; i++){
		ev.push_back({1, in[1][S[i]], 					in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
		ev.push_back({3, in[1][S[i]] + sz[1][S[i]] - 1, in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
	}
	sort(ev.begin(), ev.end());
	for (auto& [t, x, l, r, id]: ev) {
		if (t == 1) {
			rs[id] -= query(r) - query(l - 1);
		}
		else if (t == 2) {
			add(l, 1);
		}
		else {
			rs[id] += query(r) - query(l - 1);
		}
	}
	for (int i = 0; i < Q; i++){
		rs[i] = !!rs[i];
	}
	return rs;
}

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