제출 #159333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159333		iefnah06	늑대인간 (IOI18_werewolf)	C++11	100 / 100	1322 ms	155152 KiB

werewolf

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

using ll = long long;

const int MAXN = 200010;
int N, M, Q;

vector<int> adj[MAXN];
int par[MAXN];
const int MAXL = 20;
int anc[2][MAXL][MAXN];
vector<int> tr[MAXN];

void reset() {
	fill_n(par, N, -1);
	for (int i = 0; i < N; i++) tr[i].clear();
}
int getpar(int a) {
	return par[a] == -1 ? a : par[a] = getpar(par[a]);
}

int st[MAXN], ed[MAXN];
int ind;

void dfs(int cur = 0) {
	st[cur] = ind++;
	for (int nxt : tr[cur]) {
		dfs(nxt);
	}
	ed[cur] = ind;
}

const int MAXQ = 200010;
vector<int> queries[MAXN];
int ql[MAXQ], qr[MAXQ];
vector<int> ans;

struct seg {
	seg* ch[2] = {nullptr, nullptr};
};

void update(int p, seg* &n, int x = 0, int y = N) {
	if (!n) {
		n = new seg();
	}
	if (y - x > 1) {
		int z = (x + y) / 2;
		if (p < z) {
			update(p, n->ch[0], x, z);
		} else {
			update(p, n->ch[1], z, y);
		}
	}
}

int query(int l, int r, seg* n, int x = 0, int y = N) {
	if (!n) {
		return 0;
	}
	if (l <= x && y <= r) {
		return 1;
	} else {
		int z = (x + y) / 2;
		if (l < z && query(l, r, n->ch[0], x, z)) return 1;
		if (z < r && query(l, r, n->ch[1], z, y)) return 1;
		return 0;
	}
}

seg* merge(seg* a, seg* b) {
	if (!a) return b;
	if (!b) return a;
	a->ch[0] = merge(a->ch[0], b->ch[0]);
	a->ch[1] = merge(a->ch[1], b->ch[1]);
	return a;
}

seg* roots[MAXN];

void go(int cur = N - 1) {
	for (int nxt : tr[cur]) {
		go(nxt);
		roots[cur] = merge(roots[cur], roots[nxt]);
	}
	update(st[cur], roots[cur]);
	for (int q : queries[cur]) {
		ans[q] = query(ql[q], qr[q], roots[cur]); 
	}
}

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	N = n;
	M = int(X.size());
	Q = int(S.size());

	for (int i = 0; i < M; i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	reset();
	for (int a = N - 1; a >= 0; a--) {
		for (int b : adj[a]) {
			if (b < a) continue;
			int t = getpar(b);
			if (a != t) {
				par[t] = a;
				anc[0][0][t] = a;
				tr[a].push_back(t);
			}
		}
	}
	anc[0][0][0] = -1;

	dfs();

	reset();
	for (int a = 0; a < N; a++) {
		for (int b : adj[a]) {
			if (b > a) continue;
			int t = getpar(b);
			if (a != t) {
				par[t] = a;
				anc[1][0][t] = a;
				tr[a].push_back(t);
			}
		}
	}
	anc[1][0][N - 1] = -1;

	for (int t = 0; t < 2; t++) {
		for (int l = 1; l < MAXL; l++) {
			for (int i = 0; i < N; i++) {
				if (anc[t][l - 1][i] == -1) {
					anc[t][l][i] = -1;
				} else {
					anc[t][l][i] = anc[t][l - 1][anc[t][l - 1][i]];
				}
			}
		}
	}
	
	for (int q = 0; q < Q; q++) {
		int a = S[q], b = E[q];
		for (int l = MAXL - 1; l >= 0; l--) {
			if (anc[0][l][a] != -1 && anc[0][l][a] >= L[q]) {
				a = anc[0][l][a];
			}
		}
		for (int l = MAXL - 1; l >= 0; l--) {
			if (anc[1][l][b] != -1 && anc[1][l][b] <= R[q]) {
				b = anc[1][l][b];
			}
		}

		ql[q] = st[a];
		qr[q] = ed[a];
		queries[b].push_back(q);
	}

	ans = vector<int>(Q);
	go();

	return ans;
}

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