#include<bits/stdc++.h>
#pragma GCC optimization ("O2")
#include "werewolf.h"
using namespace std;
const int nax = 2e5 + 10;
int rep1[nax], rep2[nax];
pair<int,int> x_co[nax * 2], y_co[nax * 2];
int tt;
int cnt[nax];
struct DSU {
int par[nax], sz[nax];
DSU() {
for(int i=0; i<nax; ++i) {
sz[i] = 1, par[i] = i;
}
}
int find(int v) {
return par[v] = (par[v]==v) ? v : find(par[v]);
}
void unite(int u, int v) {
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
bool same(int u, int v) {
return find(u) == find(v);
}
};
struct KRT {
DSU T;
vector<int>tree[nax * 2];
int N;
int r[nax];
KRT() {
for(int i=0; i<nax; ++i) {
r[i] = i;
}
}
void add_edge(int u, int v) {
if(T.same(u, v)) return;
u = T.find(u), v = T.find(v);
tree[N].push_back(r[u]);
tree[N].push_back(r[v]);
T.unite(u, v);
r[T.find(u)] = N++;
}
int get_rep(int v) {
return r[T.find(v)];
}
} krt1, krt2;
struct BIT {
int bit[nax];
void add(int p) {
while(p<nax) {
bit[p]++;
p += p & -p;
}
}
int get(int p) {
int ret = 0;
while(p) {
ret += bit[p];
p -= p & -p;
}
return ret;
}
int get(int l, int r) {
int ret = get(r);
if(l) ret -= get(l-1);
return ret;
}
};
void DFS(int v, KRT *krt, pair<int,int> *co, int N) {
co[v].first = tt;
tt += v < N;
for(int u : krt->tree[v]) {
DFS(u, krt, co, N);
}
co[v].second = tt-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) {
int Q = S.size();
int M = X.size();
vector<pair<int,int>>edges;
for(int i=0; i<M; ++i) {
edges.emplace_back(X[i], Y[i]);
}
//build KRT1
krt1.N = N;
sort(edges.begin(), edges.end(), [&] (auto x, auto y) {
return min(x.first, x.second) > min(y.first, y.second);
});
vector<int>whosL[nax];
for(int i=0; i<Q; ++i) {
whosL[L[i]].push_back(i);
}
for(int i=0; i<Q; ++i) {
rep1[i] = S[i];
}
for(auto [u, v] : edges) {
krt1.add_edge(u, v);
for(int j : whosL[min(u, v)]) {
rep1[j] = krt1.get_rep(S[j]);
}
}
//build KRT2
krt2.N = N;
sort(edges.begin(), edges.end(), [&] (auto x, auto y) {
return max(x.first, x.second) < max(y.first, y.second);
});
vector<int>whosR[nax];
for(int i=0; i<Q; ++i) {
whosR[R[i]].push_back(i);
}
for(int i=0; i<Q; ++i) {
rep2[i] = E[i];
}
for(auto [u, v] : edges) {
krt2.add_edge(u, v);
for(int j : whosR[max(u, v)]) {
rep2[j] = krt2.get_rep(E[j]);
}
}
//rename nodes in KRT1
tt = 0;
DFS(krt1.N-1, &krt1, x_co, N);
//rename nodes in KRT2
tt = 0;
DFS(krt2.N-1, &krt2, y_co, N);
//get all points
vector<int>x_to_y[nax];
for(int i=0; i<N; ++i) {
x_to_y[x_co[i].first].push_back(y_co[i].first);
}
vector<int>left_queries[nax], right_queries[nax];
for(int i=0; i<Q; ++i) {
left_queries[x_co[rep1[i]].first].push_back(i);
right_queries[x_co[rep1[i]].second].push_back(i);
}
//sweep line
BIT b;
for(int i=0; i<N; ++i) {
//handle left side of queries
for(int j : left_queries[i]) {
cnt[j] -= b.get(y_co[rep2[j]].first+1, y_co[rep2[j]].second+1);
}
//add points
for(int y : x_to_y[i]) {
b.add(y+1);
}
//handle right side of queries
for(int j : right_queries[i]) {
cnt[j] += b.get(y_co[rep2[j]].first+1, y_co[rep2[j]].second+1);
}
}
//conclusion
vector<int>ans(Q);
for(int i=0; i<Q; ++i) {
ans[i] = cnt[i] > 0;
}
return ans;
}
Compilation message
werewolf.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O2")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
48084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
48084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
580 ms |
106812 KB |
Output is correct |
| 2 |
Incorrect |
451 ms |
113360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
48084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
