#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q, num[200200];
vector<int> ans, adj[200200];
struct Query{
int s, e, l, r, i;
Query(){}
Query(int _s, int _e, int _l, int _r, int _i): s(_s), e(_e), l(_l), r(_r), i(_i) {}
bool operator<(const Query &Q) const{
return l > Q.l;
}
};
vector<Query> Q;
struct Range{
int l, r, t;
Range(){}
Range(int _l, int _r, int _t): l(_l), r(_r), t(_t) {}
bool operator<(const Range &R) const{
return t < R.t;
}
};
vector<Range> ran[200200], root[200200];
struct DSU1{
int path[200200];
vector<int> S[200200];
void init(int n){for (int i=0;i<n;i++){path[i] = i; S[i] = {i};}}
int find(int s){
if (path[s]==s) return s;
return find(path[s]);
}
void merge(int s, int v, int t){
s = find(s), v = find(v);
if (s==v) return;
if (S[s].size() > S[v].size()) swap(s, v);
for (auto &x:S[s]){
num[x] += S[v].size();
if (!root[x].empty() && root[x].back().t==t) root[x].back().l = v;
else root[x].emplace_back(v, -1, t);
S[v].push_back(x);
}
path[s] = v;
}
void update(int s, int t){
s = find(s);
ran[s].emplace_back(S[s][0], S[s].back(), t);
}
}dsu1;
struct DSU2{
int path[200200];
set<int> S[200200];
void init(int n){for (int i=0;i<n;i++){path[i] = i; S[i].insert(i);}}
int find(int s){
if (path[s]==s) return s;
return find(path[s]);
}
void merge(int s, int v){
s = find(s), v = find(v);
if (s==v) return;
if (S[s].size() > S[v].size()) swap(s, v);
for (auto &x:S[s]) S[v].insert(x);
path[s] = v;
}
bool valid(int s, int l, int r){
s = find(s);
auto iter = S[s].lower_bound(l);
return (iter!=S[s].end() && *iter<=r);
}
}dsu2;
void init(){ ///renumbering
dsu1.init(n);
for (int i=0;i<n;i++){
root[i].emplace_back(i, -1, -1);
ran[i].emplace_back(i, i, -1);
}
for (int i=0;i<n;i++){
for (auto &v:adj[i]) if (v<i) dsu1.merge(v, i, i);
dsu1.update(i, i);
}
for (int i=0;i<n;i++){
for (auto &q:ran[i]) q.l = num[q.l], q.r = num[q.r];
}
}
pair<int, int> get_range(int s, int t){
auto iter = upper_bound(root[s].begin(), root[s].end(), Range(-1, -1, t));
s = prev(iter)->l;
iter = --upper_bound(ran[s].begin(), ran[s].end(), Range(-1, -1, t));
return {iter->l, iter->r};
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N, m = X.size(), q = S.size();
ans.resize(q);
for (int i=0;i<m;i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i=0;i<q;i++) Q.emplace_back(S[i], E[i], L[i], R[i], i);
sort(Q.begin(), Q.end());
//printf("YES\n");
init();
dsu2.init(n);
//printf("YES\n");
int pt = 0;
for (int i=n-1;i>=0;i--){
for (auto &v:adj[i]) if (v>i) dsu2.merge(num[v], num[i]);
for (;pt<q && Q[pt].l==i;pt++){
auto p = get_range(Q[pt].e, Q[pt].r);
if (dsu2.valid(Q[pt].s, p.first, p.second)) ans[Q[pt].i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
603 ms |
226040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
