This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//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 = 200005;
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);
}
};
int n;
vc<int> t[200005 * 4];
void build(vc<int> &x, int l = 0, int r = n - 1, int v = 1) {
if (l == r) return void(t[v] = {x[l]});
int mid = (l + r) / 2;
build(x, l, mid, v * 2), build(x, mid + 1, r, v * 2 + 1);
t[v].resize(t[v * 2].size() + t[v * 2 + 1].size());
merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
}
bool check(int l_, int r_, int a, int b, int l = 0, int r = n - 1, int v = 1) {
if (l_ <= l && r <= r_) {
auto y = lower_bound(t[v].begin(), t[v].end(), a);
return y != t[v].end() && *y <= b;
}
if (r < l_ || r_ < l) return false;
int mid = (l + r) / 2;
return check(l_, r_, a, b, l, mid, v * 2) || check(l_, r_, a, b, mid + 1, r, v * 2 + 1);
}
vector<int>
check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
::n = N;
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);
sort(ord.begin(), ord.end(), [&](const int &i, const int &j) { return R[i] < R[j]; });
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;
}
sort(ord.begin(), ord.end(), [&](const int &i, const int &j) { return L[i] > L[j]; }), 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> wh(N);
for (int i = 0; i < N; ++i) wh[b.ei[i]] = i;
vc<int> bip(N);
for (int i = 0; i < N; ++i) {
bip[i] = wh[a.ei[i]];
}
build(bip);
for (int i = 0; i < ans.size(); ++i) {
ans[i] = check(a.f[t1[i]], a.s[t1[i]] - 1, b.f[t2[i]], b.s[t2[i]] - 1);
}
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
Compilation message (stderr)
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < X.size(); ++i) {
| ~~^~~~~~~~~~
werewolf.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while (j < ord.size() && R[ord[j]] == v) t1[ord[j]] = a.get(E[ord[j]]), ++j;
| ~~^~~~~~~~~~~~
werewolf.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while (j < ord.size() && L[ord[j]] == v) t2[ord[j]] = b.get(S[ord[j]]), ++j;
| ~~^~~~~~~~~~~~
werewolf.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 0; i < ans.size(); ++i) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |