| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 600729 | vovik | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _GLIBCXX_DEBUG
//I wrote this code 4 u today
#include <bits/stdc++.h>
#define vc vector
#define nd node*
#define pnd pair<nd, nd>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;
template<const ll MOD>
struct mod_mul : multiplies<const ll> {
ll operator()(const ll a, const ll b) {
return (a * b) % MOD;
}
};
template<typename T>
inline void sort(T &a) {
sort(a.begin(), a.end());
}
template<typename T>
inline void unique(T &a) {
a.resize(unique(a.begin(), a.end()) - a.begin());
}
template<typename T>
inline void reverse(T &a) {
reverse(a.begin(), a.end());
}
const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;
struct DSU {
static const int MAXN = 205;
vc<int> down[MAXN];
int p[MAXN], f[MAXN], s[MAXN];
DSU() { iota(p, p + MAXN, 0); }
int get(int v) { return p[v] == v ? v : p[v] = get(p[v]); }
void merge(int v, int u) {//v->u
v = get(v), u = get(u);
if (v == u) return;
p[u] = v, down[v].push_back(u);
}
vc<int> ei;
void dfs(int v) {
f[v] = ei.size();
ei.push_back(v);
for (auto to: down[v]) dfs(to);
s[v] = ei.size();
}
void build_tour() {
for (int v = 0; v < MAXN; ++v) if (get(v) == v) dfs(v);
}
};
vector<int>
check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
vc<vc<int>> s(N), l(N);
DSU a, b;
for (int i = 0; i < X.size(); ++i) {
if (X[i] < Y[i]) swap(X[i], Y[i]);
s[X[i]].push_back(Y[i]);
l[Y[i]].push_back(X[i]);
}
vc<int> t1(S.size()), t2(S.size());
vc<int> ord(S.size());
iota(ord.begin(), ord.end(), 0);
int j = 0;
for (int v = 0; v < N; ++v) {
for (auto to: s[v]) a.merge(v, to);
while (j < ord.size() && R[ord[j]] == v) t1[ord[j]] = a.get(E[ord[j]]), ++j;
}
reverse(ord), j = 0;
for (int v = N - 1; v >= 0; --v) {
for (auto to: l[v]) b.merge(v, to);
while (j < ord.size() && L[ord[j]] == v) t2[ord[j]] = b.get(S[ord[j]]), ++j;
}
a.build_tour(), b.build_tour();
vc<int> ans(S.size());
vc<int> v(N, -1);
for (int i = 0; i < ans.size(); ++i) {
for (int j = a.f[t1[i]]; j < a.s[t1[i]]; ++j) v[a.ei[j]] = i;
for (int j = b.f[t2[i]]; j < b.s[t2[i]]; ++j) ans[i] |= v[b.ei[j]] == i;
}
return ans;
}
#ifdef VOVA
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
#endif