#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct UF {
int n;
vi e;
vector<vi> el;
UF(int N) : n(N), e(N, -1), el(N) {
for(int i = 0; i < n; ++i) el[i].push_back(i);
}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v];
for(auto it : el[v])
el[u].push_back(it);
e[v] = u;
}
void clear() {
for(auto &it : e) it = -1;
for(int i = 0; i < n; ++i) {
el[i].clear();
el[i].push_back(i);
}
}
vi acces(int u) {
return el[repr(u)];
}
};
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
vector<vi> adj(N);
for(int i = 0; i < (int)(X.size()); ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int q = L.size();
vector<vi> QL(N);
for(int i = 0; i < q; ++i) {
QL[L[i]].push_back(i);
}
/// n <= 3000 m <= 6000 q <= 3000
UF S1(N), S2(N);
vector<int> Re(q, 0);
for(int l = N - 1; l >= 0; --l) {
for(auto it : adj[l])
if(it > l)
S1.join(it, l);
sort(QL[l].begin(), QL[l].end(), [&](auto a, auto b) { return R[a] < R[b]; });
int p = 0;
S2.clear();
for(int r = 0; r < N; ++r) {
for(auto it : adj[r]) {
if(it < r)
S2.join(it, r);
}
while(p < QL[l].size() && R[QL[l][p]] == r) {
int id = QL[l][p];
vi st = S1.acces(S[id]);
vi dr = S2.acces(E[id]);
sort(st.begin(), st.end());
sort(dr.begin(), dr.end());
int pdr = 0, ok = 0;
for(int i = 0; i < st.size(); ++i) {
while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
if(pdf < dr.size() && dr[pdr] == st[i]) ok = 1;
}
Re[id] = ok;
++p;
}
}
}
return Re;
}
Compilation message
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | while(p < QL[l].size() && R[QL[l][p]] == r) {
| ~~^~~~~~~~~~~~~~
werewolf.cpp:79:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0; i < st.size(); ++i) {
| ~~^~~~~~~~~~~
werewolf.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
| ~~~~^~~~~~~~~~~
werewolf.cpp:81:24: error: 'pdf' was not declared in this scope; did you mean 'pdr'?
81 | if(pdf < dr.size() && dr[pdr] == st[i]) ok = 1;
| ^~~
| pdr
