#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct UF {
int n;
vi e, mi, ma;
vector<vi> el;
UF(int N) : n(N), e(N, -1), el(N), mi(N), ma(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];
mi[u] = min(mi[u], mi[v]);
ma[u] = max(ma[v], ma[u]);
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);
}
}
ii get_seg(int u) {
u = repr(u);
return make_pair(mi[u], ma[u]);
}
void setval(vi &V) {
for(int i = 0; i < n; ++i)
mi[i] = ma[i] = V[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(), m = X.size();
vector<vi> QL(N);
for(int i = 0; i < q; ++i) {
QL[L[i]].push_back(i);
}
/// n <= 3000 m <= 6000 q <= 3000
if(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(pdr < dr.size() && dr[pdr] == st[i]) ok = 1;
}
Re[id] = ok;
++p;
}
}
}
return Re;
} else {
///presupunem ca e o dreapta
int capat = 0;
for(int i = 0; i < N; ++i) {
if(adj[i].size() == 1) capat = i;
}
vi valori(N, 0);
function<void(int, int, int)> dfs0 = [&](int u, int p, int v) {
valori[u] = v;
for(auto it : adj[u]) {
if(it != p) {
dfs0(it, u, v + 1);
}
}
};
dfs0(capat, -1, 0);
vector<vi> QL(N), QR(N);
for(int i = 0; i < q; ++i) {
QL[L[i]].push_back(i);
QR[R[i]].push_back(i);
}
vector<ii> SegL(q), SegR(q);
UF Sol(N);
Sol.setval(valori);
for(int i = N - 1; i >= 0; --i) {
for(auto it : adj[i])
if(it > i) Sol.join(i, it);
for(auto id : QL[i]) {
SegL[id] = Sol.get_seg(S[id]);
}
}
Sol.clear();
Sol.setval(valori);
for(int i = 0; i < N; ++i) {
for(auto it : adj[i])
if(it < i) Sol.join(i, it);
for(auto id : QR[i]) {
SegR[id] = Sol.get_seg(R[id]);
}
}
vector<int> Re(q, 0);
for(int i = 0; i < q; ++i) {
if(SegL[i].second < SegR[i].first || SegR[i].second < SegL[i].first) Re[i] = 0;
else Re[i] = 1;
}
return Re;
}
}
Compilation message
werewolf.cpp: In constructor 'UF::UF(int)':
werewolf.cpp:12:16: warning: 'UF::el' will be initialized after [-Wreorder]
12 | vector<vi> el;
| ^~
werewolf.cpp:11:11: warning: 'vi UF::mi' [-Wreorder]
11 | vi e, mi, ma;
| ^~
werewolf.cpp:13:5: warning: when initialized here [-Wreorder]
13 | UF(int N) : n(N), e(N, -1), el(N), mi(N), ma(N) {
| ^~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while(p < QL[l].size() && R[QL[l][p]] == r) {
| ~~^~~~~~~~~~~~~~
werewolf.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 0; i < st.size(); ++i) {
| ~~^~~~~~~~~~~
werewolf.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
| ~~~~^~~~~~~~~~~
werewolf.cpp:94:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(pdr < dr.size() && dr[pdr] == st[i]) ok = 1;
| ~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
432 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
432 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
666 ms |
1672 KB |
Output is correct |
| 11 |
Correct |
553 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
289 ms |
1472 KB |
Output is correct |
| 13 |
Correct |
339 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
232 ms |
1644 KB |
Output is correct |
| 15 |
Correct |
616 ms |
1372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
375 ms |
101492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
432 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
666 ms |
1672 KB |
Output is correct |
| 11 |
Correct |
553 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
289 ms |
1472 KB |
Output is correct |
| 13 |
Correct |
339 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
232 ms |
1644 KB |
Output is correct |
| 15 |
Correct |
616 ms |
1372 KB |
Output is correct |
| 16 |
Incorrect |
375 ms |
101492 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
