Submission #768374

#	Time	Username	Problem	Language	Result	Execution time	Memory
768374		SanguineChameleon	Werewolf (IOI18_werewolf)	C++17	15 / 100	4045 ms	57592 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 get_root(int u, int type) {
	if (!par[u][type].second) {
		return u;
	}
	else {
		return get_root(par[u][type].second, type);
	}
}

void update(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 dfs(int u, int type) {
	cnt[u]++;
	for (auto e: ch[u][type]) {
		dfs(e.second, type);
	}
}

void add(int u, int pref, int type) {
	cnt[u]++;
	for (int i = 0; i < pref; i++) {
		dfs(ch[u][type][i].second, type);
	}
}

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]) {
				update(u, v, u, type);
			}
		}
		root[type] = get_root(1, type);
	}
	vector<int> res(Q);
	for (int i = 0; i < Q; i++) {
		L[i]++;
		R[i]++;
		int u = S[i] + 1;
		int v = E[i] + 1;
		while (u != root[0] && par[u][0].first >= L[i]) {
			u = par[u][0].second;
		}
		int pref_u = upper_bound(ch[u][0].begin(), ch[u][0].end(), make_pair(L[i], 0), greater<pair<int, int>>()) - ch[u][0].begin();
		while (v != root[1] && par[v][1].first <= R[i]) {
			v = par[v][1].second;
		}
		int pref_v = upper_bound(ch[v][1].begin(), ch[v][1].end(), make_pair(R[i], N + 1)) - ch[v][1].begin();
		for (int j = 1; j <= N; j++) {
			cnt[j] = 0;
		}
		add(u, pref_u, 0);
		add(v, pref_v, 1);
		for (int j = 1; j <= N; j++) {
			if (cnt[j] == 2) {
				res[i] = 1;
				break;
			}
		}
	}
	return res;
}

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