제출 #1029763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029763		DorostWef	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4062 ms	133836 KiB

werewolf

/* In the name of GOD */

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
const int N = 200012;
vector <int> g[N], t[2][N * 2];
int p[N * 2];
int par[2][N * 2];
int q;
int n;
int m;
int sz = N;
bool vis[N * 2];

void clear () {
	sz = N;
	for (int i = 0; i < N * 2; i++) 
		p[i] = i;
}

int get_par (int v) {
	return (p[v] == v ? v : p[v] = get_par (p[v]));
}

void merge (int u, int v, int i) {
	u = get_par (u);
	v = get_par (v);
	if (u == v)
		return;
	sz++;
	p[u] = sz;
	p[v] = sz;
	t[i][sz].push_back(v);
	t[i][sz].push_back(u);
}

struct que {
	int s, e, l, r;
	int v1, v2;
} qu[N];

vector <int> ll[N], rr[N];
int st [2][N * 2], ft [2][N * 2];
int ti = 1;

void dfs (int v, int i) {
	vis[v] = true;
	st[i][v] = ti;
	for (int u : t[i][v])
		dfs (u, i);
	if (v < N)
		ti++;
	ft[i][v] = ti;
}

const int SegN = N * 4;
vector <int> seg[SegN];
int aa[N];

void build (int v = 1, int tl = 0, int tr = n - 1) {
	if (tl == tr) {
		seg[v] = {aa[tl]};
		return;
	}
	int mid = (tl + tr) >> 1;
	build (v << 1, tl, mid);
	build (v << 1 | 1, mid + 1, tr);
	merge(seg[v << 1].begin(), seg[v << 1].end(), seg[v << 1 | 1].begin(), seg[v << 1 | 1].end(), back_inserter(seg[v]));
}

int get (int l, int r, int s, int e, int v = 1, int tl = 0, int tr = n - 1) {
	if (l > tr || tl > r)
		return 0;
	if (l <= tl && tr <= r) {
		if (lower_bound(seg[v].begin(), seg[v].end(), s) == upper_bound (seg[v].begin(), seg[v].end(), e)) {
			return 0;
		}
		return 1;
	}
	int mid = (tl + tr) >> 1;
	return get (l, r, s, e, v << 1, tl, mid) | get (l, r, s, e, v << 1 | 1, mid + 1, tr);
}

std::vector<int> check_validity(int NN, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    q = S.size();
    n = NN;
    m = X.size();
	for (int i = 0; i < m; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for (int i = 0; i < q; i++) {
		qu[i].s = S[i];
		qu[i].e = E[i];
		qu[i].l = L[i];
		qu[i].r = R[i];
		ll[L[i]].push_back(i);
		rr[R[i]].push_back(i);
	}
	clear();
	for (int i = 0; i < n; i++) {
		for (int j : g[i]) {
			if (j < i)
				merge (i, j, 0);
		}
		for (int j : rr[i]) {
			qu[j].v1 = get_par (qu[j].e);
		}
	}
	clear();
	for (int i = n - 1; i >= 0; i--) {
		for (int j : g[i]) 
			if (j > i)
				merge (i, j, 1);
		for (int j : ll[i]) {
			qu[j].v2 = get_par (qu[j].s);
		}
	}
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[0][i].empty()) {
			dfs (i, 0);
		}
	}
	ti = 1;
	for (int i = 0; i < 2 * N; i++)
		vis[i] = false;
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[1][i].empty()) {
			dfs (i, 1);
		}
	}
	for (int i = 0; i < 2 * N; i++) {
		ft[0][i]--;
		ft[1][i]--;
	}
	for (int i = 0; i < n; i++)
		aa[st[0][i]] = st[1][i];
	build ();
	vector <int> wef;
	for (int i = 0; i < q; i++) {
		int f = 0;
		for (int j = st[0][qu[i].v1]; j <= ft[0][qu[i].v1]; j++) {
			if (aa[j] >= st[1][qu[i].v2] && aa[j] <= ft[1][qu[i].v2])
				f = 1;
		}
		wef.push_back(f);
//		wef.push_back(get (st[0][qu[i].v1], ft[0][qu[i].v1], st[1][qu[i].v2], ft[1][qu[i].v2]));
	}
	return wef;
}

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