Submission #768378

#	Time	Username	Problem	Language	Result	Execution time	Memory
768378		SanguineChameleon	Werewolf (IOI18_werewolf)	C++17	0 / 100	2709 ms	71388 KiB

werewolf

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

const int maxN = 2e5 + 20;
vector<int> adj[maxN][2];
vector<pair<int, int>> ch[maxN][2];
pair<int, int> par[maxN][2];
int depth[maxN][2];
int cnt[maxN];
int root[2];
int Tin[maxN];
int Tout[maxN];
vector<vector<pair<int, pair<int, int>>>> queries[maxN];
vector<int> res;
int T;

int get_root(int u, int type) {
	if (!par[u][type].second) {
		return u;
	}
	else {
		return get_root(par[u][type].second, type);
	}
}

void join(int u, int v, int w, int type) {
	int ru = get_root(u, type);
	int rv = get_root(v, type);
	if (ru == rv) {
		return;
	}
	if (depth[ru][type] > depth[rv][type]) {
		swap(ru, rv);
	}
	ch[rv][type].emplace_back(w, ru);
	par[ru][type] = make_pair(w, rv);
	if (depth[ru][type] == depth[rv][type]) {
		depth[rv][type]++;
	}
}

void dfs1(int u) {
	Tin[u] = ++T;
	for (auto e: ch[u][1]) {
		dfs1(e.second);
	}
	Tout[u] = T;
}

void update(int u, int add) {
	cnt[u] += add;
}

int get(int lt, int rt) {
	int res = 0;
	for (int i = lt; i <= rt; i++) {
		res += cnt[i];
	}
	return res;
}

void dfs2(int u, int add) {
	update(u, add);
	for (auto e: ch[u][0]) {
		dfs2(e.second, add);
	}
}

void solve(int u) {
	for (int iter = 0; iter < 2; iter++) {
		int add = (iter ? -1 : 1);
		for (int i = 0; i <= (int)ch[u][0].size(); i++) {
			if (i == 0) {
				update(u, add);
			}
			else {
				dfs2(ch[u][0][i - 1].second, add);
			}
			if (!iter) {
				for (auto q: queries[u][i]) {
					int id = q.first;
					int lt = q.second.first;
					int rt = q.second.second;
					res[id] = get(lt, rt) > 0;
				}
			}
		}
	}
}

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();
	int Q = S.size();
	for (int i = 0; i < M; i++) {
		X[i]++;
		Y[i]++;
		if (X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
		adj[X[i]][0].push_back(Y[i]);
		adj[Y[i]][1].push_back(X[i]);
	}
	for (int type = 0; type < 2; type++) {
		for (int u = (type ? 1 : N); (type ? u <= N : u >= 1); u += (type ? 1 : -1)) {
			for (auto v: adj[u][type]) {
				join(u, v, u, type);
			}
		}
		root[type] = get_root(1, type);
	}
	dfs1(root[1]);
	for (int u = 1; u <= N; u++) {
		queries[u].resize(ch[u][0].size() + 1);
	}
	res.resize(Q);
	for (int id = 0; id < Q; id++) {
		L[id]++;
		R[id]++;
		int u = S[id] + 1;
		int v = E[id] + 1;
		while (u != root[0] && par[u][0].first >= L[id]) {
			u = par[u][0].second;
		}
		int pref_u = upper_bound(ch[u][0].begin(), ch[u][0].end(), make_pair(L[id], 0), greater<pair<int, int>>()) - ch[u][0].begin();
		while (v != root[1] && par[v][1].first <= R[id]) {
			v = par[v][1].second;
		}
		int pref_v = upper_bound(ch[v][1].begin(), ch[v][1].end(), make_pair(R[id], N + 1)) - ch[v][1].begin();
		for (int j = 1; j <= N; j++) {
			cnt[j] = 0;
		}
		int lt = Tin[v];
		int rt = (pref_v ? Tout[ch[v][1][pref_v - 1].second] : lt);
		queries[u][pref_u].emplace_back(id, make_pair(lt, rt));
	}
	for (int u = 1; u <= N; u++) {
		solve(u);
	}
	return res;
}

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