Submission #1191489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191489		vidux	Werewolf (IOI18_werewolf)	C++17	0 / 100	4090 ms	13956 KiB

werewolf

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

typedef vector<int> vi;
typedef vector<vi> vvi;

class DSU {
	vi size, par;
	int sz;

	public:
	DSU(int n) {
		sz = n;
		size = vi(sz, 1);
		par = vi(sz);
		for (int i = 0; i < sz; i++) par[i] = i;
	}
	int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
	bool connected(int x, int y) { return find(x) == find(y); }
	bool join(int x, int y) {
		if (connected(x, y)) return false;
		int px = find(x), py = find(y);
		if (size[px] < size[py]) swap(px, py);
		size[px] += size[py];
		par[py] = px;
		return true;
	}
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int Q = L.size();
	int M = X.size();
	vi ans(N);
	for (int t = 0; t < Q; t++) {
		DSU dsuW(N), dsuH(N);
		int l = L[t], r = R[t];
		for (int i = 0; i < M; i++) {
			if (X[i] >= l && Y[i] >= l) dsuH.join(X[i], Y[i]);
			if (X[i] <= r && Y[i] <= r) dsuW.join(X[i], Y[i]);
		}
		for (int i = 0; i < M; i++) {
			if (i >= l && i <= r) {
				if (dsuH.find(S[t]) == dsuH.find(i) && dsuW.find(E[t]) == dsuW.find(i)) {
					ans[t] = 1;
					break;
				}
			}
		}
	}
	
	return ans;
}

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