#define SHINLENA2
#ifndef SHINLENA
#include "werewolf.h"
#endif
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cstddef>
#include <cassert>
using namespace std;
#define NN 200000
struct kruskal_reconstruction_tree
{
vector<int> p, tin, tout;
int l, n0;
vector<vector<int>> g;
vector<pair<int, int>> ch;
kruskal_reconstruction_tree(int n, int n0) : p(n), tin(n), tout(n), l(n0), n0(n0), g(n), ch(n-n0, {-1,-1})
{
iota(p.begin(), p.end(), 0);
}
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
int unite(int x, int y)
{
x = find(x); y = find(y);
if (x == y) return 0;
ch[p[x] = p[y] = ++l] = {x, y};
return 1;
}
int timer = 0;
void dfs(int u)
{
tin[u] = timer++;
for (auto v : {ch[u].first, ch[u].second}) if (v != -1) dfs(v);
tout[u] = timer - 1;
}
void tour()
{
for (int i = l +1; i--;) if (!tin[i]) dfs(i);
}
};
vector<int> t[NN<<3];
void add(int v, int l, int r, int p, int k)
{
t[v].push_back(k);
if (l == r) return;
if (p <= (l+r)/2) add(2*v+1, l, (l+r)/2, p, k);
else add(2*v+2, (l+r)/2+1, r, p, k);
}
int qry(int v, int l, int r, int x, int y, int k)
{
if (r < x || y < l) return 1e9;
if (x <= l && r <= y)
{
auto it = lower_bound(t[v].begin(), t[v].end(), k);
return it == t[v].end() ? 1e9 : *it;
}
return min(qry(2*v+1, l, (l+r)/2, x, y, k), qry(2*v+2, (l+r)/2+1, r, x, y, k));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int M = X.size();
kruskal_reconstruction_tree k[2] {kruskal_reconstruction_tree(N+M, N-1), kruskal_reconstruction_tree(N+M, N-1)};
int Q = S.size();
vector<int> A(Q);
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
/* build krt */
vector<int> rtl(Q), rtr(Q);
{
vector<vector<int>> byl(N), byr(N);
for (int i = 0; i < Q; ++i) byl[L[i]].push_back(i), byr[R[i]].push_back(i);
for (int i = N; i--;)
{
for (auto v : g[i]) if (v >= i) k[0].unite(v, i);
for (auto j : byl[i]) rtl[j] = k[0].find(S[j]);
}
for (int i = 0; i < N; ++i)
{
for (auto v : g[i]) if (v <= i) k[1].unite(v, i);
for (auto j : byr[i]) rtr[j] = k[1].find(E[j]);
}
}
for (int i : {0, 1}) k[i].tour();
int LL = k[0].timer - 1;
/* build merge sort tree */
{
vector<pair<int, int>> ins;
for (int i = 0; i < N; ++i)
ins.emplace_back(k[1].tin[i], k[0].tin[i]);
sort(ins.begin(), ins.end());
for (auto [x, y] : ins) add(0, 0, LL, y, x);
}
for (int i = 0; i < Q; ++i)
{
A[i] = qry(0, 0, LL, k[0].tin[rtl[i]], k[0].tout[rtl[i]], k[1].tin[rtr[i]]) <= k[1].tout[rtr[i]];
}
return A;
}
#ifdef SHINLENA
int main()
{
int n,m,q;
cin>>n>>m>>q;
vector<int>x,y,s,e,l,r;
for (int u,v,i=0;i<m;++i)cin>>u>>v, x.push_back(u), y.push_back(v);
for (int a,b,c,d,i=0;i<q;++i)
{
cin>>a>>b>>c>>d;
s.push_back(a);
e.push_back(b);
l.push_back(c);
r.push_back(d);
}
auto A = check_validity(n,x,y,s,e,l,r);
for (auto x : A) cout << x << endl;
return 0;
}
#endif
/*
6 6 3
5 1
1 3
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
37980 KB |
Output is correct |
| 2 |
Runtime error |
435 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
37980 KB |
Output is correct |
| 2 |
Runtime error |
435 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
244356 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
37980 KB |
Output is correct |
| 2 |
Runtime error |
435 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
