#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define pi pair<int, int>
#define f first
#define s second
#define mp make_pair
vector<int> adj[200000];
int id[200000];
int idRev[200000];
int id2[200000];
int id2Rev[200000];
bool vis[200000];
pi rangeL[200000];
pi rangeR[200000];
int pa[200000];
int sz[200000];
pi range[200000];
int get(int x) {
return pa[x] == x ? x : pa[x] = get(pa[x]);
}
void unite(int a, int b) {
a = get(a), b = get(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
pa[a] = b;
sz[b] += sz[a];
range[b].f = min(range[b].f, range[a].f);
range[b].s = max(range[b].s, range[a].s);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i < (int)X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int ctr = 0;
priority_queue<int, vector<int>, greater<int>> q;
q.push(0); vis[0] = true;
while (!q.empty()) {
int u = q.top(); q.pop();
idRev[ctr] = u;
id[u] = ctr++;
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
for (int i = 0; i < N; i++) vis[i] = 0;
ctr = 0;
priority_queue<int> q2;
q2.push(N-1); vis[N-1] = true;
while (!q2.empty()) {
int u = q2.top(); q2.pop();
id2Rev[ctr] = u;
id2[u] = ctr++;
//cout << u << " is " << ctr-1 << endl;
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q2.push(v);
}
}
}
vector<int> queries;
for (int i = 0; i < S.size(); i++) {
queries.push_back(i);
}
int qryIdx = 0;
sort(queries.begin(), queries.end(), [&R](int a, int b) {
return R[a] < R[b];
});
for (int i = 0; i < N; i++) range[i] = mp(id[i], id[i]), pa[i] = i, sz[i] = 1;
for (int i = 0; i < N; i++) {
for (int v : adj[i]) {
if (v < i) unite(i, v);
}
while (qryIdx < S.size() && R[queries[qryIdx]] <= i) {
rangeR[queries[qryIdx]] = range[get(E[queries[qryIdx]])];
qryIdx++;
}
}
qryIdx = 0;
sort(queries.begin(), queries.end(), [&L](int a, int b) {
return L[a] > L[b];
});
for (int i = 0; i < N; i++) range[i] = mp(id2[i], id2[i]), pa[i] = i, sz[i] = 1;
for (int i = N-1; ~i; i--) {
for (int v : adj[i]) {
if (v > i) unite(i, v);
}
while (qryIdx < S.size() && L[queries[qryIdx]] >= i) {
rangeL[queries[qryIdx]] = range[get(S[queries[qryIdx]])];
qryIdx++;
}
}
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
pi lrange = rangeL[i], rrange = rangeR[i];
//cout << i << ": (" << lrange.f << "," << lrange.s << ") -- (" << rrange.f << "," << rrange.s << ")\n";
A[i] = 0;
set<int> lft2;
for (int j = lrange.f; j <= lrange.s; j++) {
assert(id2Rev[j] >= L[i]);
lft2.insert(id2Rev[j]);
}
for (int j = rrange.f; j <= rrange.s; j++) {
assert(idRev[j] <= R[i]);
if (lft2.count(idRev[j])) A[i] = 1;
}
assert(E[i] <= R[i]);
assert(S[i] >= L[i]);
A[i] = 0;
queue<int> q;
set<int> lft;
set<int> rht;
q.push(S[i]); lft.insert(S[i]);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (v >= L[i] && !lft.count(v)) {
lft.insert(v);
q.push(v);
}
}
}
assert(lft2.size() <= lft.size());
q.push(E[i]); rht.insert(E[i]);
while (!q.empty()) {
int u = q.front(); q.pop();
if (lft.count(u)) A[i] = 1;
for (int v : adj[u]) {
if (v <= R[i] && !rht.count(v)) {
rht.insert(v);
q.push(v);
}
}
}
}
return A;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
werewolf.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while (qryIdx < S.size() && R[queries[qryIdx]] <= i) {
| ~~~~~~~^~~~~~~~~~
werewolf.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | while (qryIdx < S.size() && L[queries[qryIdx]] >= i) {
| ~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
41432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
