제출 #1198141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198141		dubabuba	Werewolf (IOI18_werewolf)	C++20	15 / 100	577 ms	9796 KiB

werewolf

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

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int mxn = 3030;
int n, m, q, par[mxn];

int parent(int u) { return par[u] < 0 ? u : par[u] = parent(par[u]); }
bool unite(int u, int v, string debug = "") {
	if(debug.size()) {
		cout << debug << ": " << u << ' ' << v << endl;
	}

	u = parent(u);
	v = parent(v);
	if(u == v) return 0;

	if(par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return 1;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n = N;
	m = X.size();
	q = S.size();

	vi ret;
	for(int i = 0; i < q; i++) {
		int s = S[i];
		int e = E[i];
		int l = L[i];
		int r = R[i];

		memset(par, -1, sizeof(int) * n);
		for(int i = 0; i < m; i++) {
			if(X[i] >= l && Y[i] >= l)
			unite(X[i], Y[i]);
		}
		
		bitset<mxn> st = 0;
		for(int i = l; i <= r; i++)
			if(parent(i) == parent(s))
				st[i] = 1;

		memset(par, -1, sizeof(int) * n);
		for(int i = 0; i < m; i++) {
			if(X[i] <= r && Y[i] <= r)
			unite(X[i], Y[i]);
		}
		
		bitset<mxn> en = 0;
		for(int i = 0; i < n; i++)
			if(parent(i) == parent(e))
				en[i] = 1;

		bitset<mxn> cnt = st & en;
		if(cnt.count())
			ret.push_back(1);
		else
			ret.push_back(0);
	}
	return ret;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

*/

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