제출 #144005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144005		Minnakhmetov	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4030 ms	88584 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 4e5 + 5, L = 20;
int w[N], tin[2][N], tout[2][N], p[2][N][L];
vector<int> g[N], tr[2][N];
int timer;

int findSet(int v) {
	return w[v] < 0 ? v : w[v] = findSet(w[v]);
}

void connect(int a, int b, int type) {
	a = findSet(a);
	b = findSet(b);

	if (a != b) {
		w[a] += w[b];
    	w[b] = a;
    	tr[type][a].push_back(b);
	}
}

void dfs(int node, int p[N][L], int tin[N], int tout[N], vector<int> tr[N]) {
	tin[node] = ++timer;
	for (int i = 1; i < L; i++) {
		p[node][i] = p[p[node][i - 1]][i - 1];
	}
	for (int to : tr[node]) {
		p[to][0] = node;
		dfs(to, p, tin, tout, tr);
	}
	tout[node] = timer;
}

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 q = s.size(), m = x.size();
	vector<int> ans(q);

	for (int i = 0; i < m; i++) {
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}

	fill(w, w + n, -1);

	for (int i = n - 1; i >= 0; i--) {
		for (int to : g[i]) {
			if (to > i) {
				connect(i, to, 0);
			}
		}
	}

	fill(w, w + n, -1);

	for (int i = 0; i < n; i++) {
		for (int to : g[i]) {
			if (to < i) {
				connect(i, to, 1);
			}
		}
	}

	// for (int i = 0; i < 2; i++) {
	// 	for (int j = 0; j < n; j++) {
	// 		for (int to : tr[i][j]) {
	// 			cout << j << " " << to << "\n";
	// 		}
	// 	}
	// 	cout << "\n";
	// }

	timer = -1;
	dfs(0, p[0], tin[0], tout[0], tr[0]);

	timer = -1;
	fill(p[1][n - 1], p[1][n - 1] + L, n - 1);
	dfs(n - 1, p[1], tin[1], tout[1], tr[1]);

	for (int i = 0; i < q; i++) {
		int v1 = s[i], v2 = e[i];

		for (int j = L - 1; j >= 0; j--) {
			if (p[0][v1][j] >= l[i]) {
				v1 = p[0][v1][j];
			}
		}

		for (int j = L - 1; j >= 0; j--) {
			if (p[1][v2][j] <= r[i]) {
				v2 = p[1][v2][j];
			}
		}

		for (int j = l[i]; j <= r[i]; j++) {
			if (tin[0][j] >= tin[0][v1] && tin[0][j] <= tout[0][v1] &&
				tin[1][j] >= tin[1][v2] && tin[1][j] <= tout[1][v2]) {
				ans[i] = 1;
			}
		}
	}

  	return ans;
}

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