제출 #75006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75006		ainta	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1850 ms	146652 KiB

werewolf

#include "werewolf.h"
#include<algorithm>
#include<vector>
#define N_ 201000
#define M_ 401000
using namespace std;


int n, m, Q, UF[N_], par[N_][2][20], Num[N_][2], Ed[N_][2], cnt, ReNum[N_][2];
vector<int> UU[N_], DD[N_];
vector<int> T[N_][2];

int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}

void DFS(int a, int ck) {
	Num[a][ck] = ++cnt;
	ReNum[cnt][ck] = a;
	for (auto &x : T[a][ck]) {
		par[x][ck][0] = a;
		DFS(x, ck);
	}
	Ed[a][ck] = cnt;
}

struct PST {
	int l, r, s;
}IT[N_*20];
int Root[N_], cc;

void Put(int rt, int cur, int b, int e, int x) {
	IT[cur] = IT[rt];
	if (b == e) {
		IT[cur].s++;
		return;
	}
	int m = (b + e) >> 1;
	cc++;
	if (x <= m) {
		IT[cur].l = cc;
		Put(IT[rt].l, IT[cur].l, b, m, x);
	}
	else {
		IT[cur].r = cc;
		Put(IT[rt].r, IT[cur].r, m + 1, e, x);
	}
	IT[cur].s = IT[IT[cur].l].s + IT[IT[cur].r].s;
}

int Sum(int nd, int b, int e, int s, int l) {
	if (b == s && e == l)return IT[nd].s;
	int m = (b + e) >> 1, r = 0;
	if (s <= m) r += Sum(IT[nd].l, b, m, s, min(m, l));
	if (l > m)r += Sum(IT[nd].r, m + 1, e, max(m + 1, s), l);
	return r;
}

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 = X.size();
	Q = S.size();
	int i, j;
	for (i = 0; i < n; i++)UF[i] = i;
	for (i = 0; i < m; i++) {
		int x = X[i], y = Y[i];
		if (x > y)swap(x, y);
		UU[x].push_back(y);
		DD[y].push_back(x);
	}
	for (i = 0; i < n; i++) {
		for (auto &x : DD[i]) {
			int y = Find(x);
			if (y == i)continue;
			T[i][0].push_back(y);
			UF[y] = i;
		}
	}
	for (i = 0; i < n; i++)UF[i] = i;
	for (i = n - 1; i >= 0; i--) {
		for (auto &x : UU[i]) {
			int y = Find(x);
			if (y == i)continue;
			T[i][1].push_back(y);
			UF[y] = i;
		}
	}
	cnt = 0;
	DFS(n - 1, 0);
	cnt = 0;
	DFS(0, 1);
	par[n - 1][0][0] = n - 1;
	par[0][1][0] = 0;
	for (i = 0; i < 18; i++) {
		for (j = 0; j < n; j++) {
			par[j][0][i + 1] = par[par[j][0][i]][0][i];
			par[j][1][i + 1] = par[par[j][1][i]][1][i];
		}
	}


	for (i = 1; i <= n; i++) {
		Root[i] = ++cc;
		int x = ReNum[i][0];
		Put(Root[i - 1], Root[i], 1, n, Num[x][1]);
	}

	vector<int>ret;

	for (i = 0; i < Q; i++) {
		int x = S[i], y = E[i];
		for (j = 18; j >= 0; j--) {
			if (par[x][1][j] >= L[i])x = par[x][1][j];
			if (par[y][0][j] <= R[i])y = par[y][0][j];
		}
		if (Sum(Root[Ed[y][0]], 1, n, Num[x][1], Ed[x][1]) - Sum(Root[Num[y][0] - 1], 1, n, Num[x][1], Ed[x][1]) > 0)ret.push_back(1);
		else ret.push_back(0);
	}
	return ret;
}

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