| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1191488 | vidux | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
#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;
}
int main() {
int N, M, Q; cin >> N >> M >> Q;
vi X(M), Y(M);
vi S(Q), E(Q), L(Q), R(Q);
for (int i = 0; i < M; i++) cin >> X[i] >> Y[i];
for (int i = 0; i < Q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
vi ans = check_validity(N, X, Y, S, E, L, R);
for (int i = 0; i < Q; i++) cout << ans[i] << endl;
return 0;
}