#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5 + 10;
int fen[N];
void modif(int u, int val) {
for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
int query(int l, int r) {
int ans = 0;
for(int i = r + 1; i > 0; i -= i & -i) ans += fen[i];
for(int i = l; i > 0; i -= i & -i) ans += fen[i];
return ans;
}
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n); iota(p.begin(), p.end(), 0);
}
int get(int a) {
return p[a] = (a == p[a] ? a : get(p[a]));
}
void uni(int a, int b, vector<vector<int>>& adj) {
a = get(a), b = get(b);
if(a == b) return;
p[a] = b; adj[b].push_back(a);
}
};
void dfs(int u, vector<int>& p, vector<int>& s, vector<vector<int>>& adj, int tt = 0) {
p[u] = tt++;
s[u] = 1;
for(int v: adj[u]) {
dfs(v, p, s, adj, tt);
s[u] += s[v];
}
}
std::vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, std::vector<int> E,
vector<int> L, std::vector<int> R) {
int Q = S.size();
vector<int> ans(Q, 0);
vector<vector<int>> g1(n), g2(n), g(n);
for(int i = 0; i < X.size(); ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
dsu d1(n), d2(n);
for(int i = 0; i < n; ++i) {
for(int j: g[i]) if(i > j) d1.uni(i, j, g1);
}
for(int i = n - 1; i >= 0; --i) {
for(int j: g[i]) if(i < j) d2.uni(i, j, g2);
}
vector<int> p1(n), s1(n), p2(n), s2(n);
dfs(d1.get(0), p1, s1, g1), dfs(d2.get(n - 1), p2, s2, g2);
vector<int> events[n];
for(int i = 0; i < Q; ++i) {
int node = d1.get(L[i]);
events[p1[node]].push_back(-1);
events[p1[node] + s1[node] - 1].push_back(i);
}
for(int i = 0; i < n; ++i) {
sort(events[i].begin(), events[i].end());
for(int j: events[i]) {
if(j < 0) {
modif(i, 1);
} else {
int node = d2.get(R[j]);
if(query(p2[node], p2[node] + s2[node] - 1)) ans[j] = 1;
}
}
for(int j: events[i]) if(j >= 0) modif(i, -1);
}
return ans;
}
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:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < X.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
328 ms |
55276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
