#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct dsu
{
vector<int> p;
vector<vector<int>> g;
dsu(size_t n) { p = vector<int>(n, -1), g.resize(n); }
int repr(int u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }
void add_node(int u, vector<int> const &adj)
{
for (auto const &v : adj)
if (repr(v) != u)
g[u].push_back(repr(v)), p[repr(v)] = u;
}
int dfs(vector<pair<int, int>> &subtree_range, int u, int i = 0)
{
subtree_range[u].first = i++;
for (int const &v : g[u])
i = dfs(subtree_range, v, i);
subtree_range[u].second = i - 1;
return i;
}
vector<pair<int, int>> euler_tour()
{
vector<vector<int>> g(p.size());
int root = -1;
for (int i = 0; i < p.size(); ++i)
if (p[i] == -1)
root = i;
assert(root != -1);
vector<pair<int, int>> subtree_range(p.size());
dfs(subtree_range, root);
return subtree_range;
}
};
struct fenwick_tree
{
vector<int> t;
fenwick_tree(size_t n) { t.resize(n); }
void update(int i, int x)
{
++i;
while (i <= t.size())
t[i - 1] += x, i += i & -i;
}
int range_sum(int i, int j)
{
int x = 0;
++j;
while (j)
x += t[j - 1], j -= j & -j;
while (i)
x -= t[i - 1], i -= i & -i;
return x;
}
};
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 const Q = S.size();
vector<vector<int>> g(N);
for (size_t i = 0; i < X.size(); ++i)
g[min(X[i], Y[i])].push_back(max(X[i], Y[i]));
vector<int> root1(Q), p(Q);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&L](int const &i, int const &j)
{ return L[i] > L[j]; });
dsu d(N);
for (int i = N - 1, j = 0; i >= 0; --i)
{
d.add_node(i, g[i]);
while (j < p.size() && L[p[j]] == i)
root1[p[j]] = d.repr(S[p[j]]), ++j;
}
vector<pair<int, int>> subtree_range1 = d.euler_tour();
for (int i = 0; i < N; ++i)
g[i].clear();
for (size_t i = 0; i < X.size(); ++i)
g[max(X[i], Y[i])].push_back(min(X[i], Y[i]));
vector<int> root2(Q);
sort(p.begin(), p.end(), [&R](int const &i, int const &j)
{ return R[i] < R[j]; });
d = dsu(N);
for (int i = 0, j = 0; i < N; ++i)
{
d.add_node(i, g[i]);
while (j < p.size() && R[p[j]] == i)
root2[p[j]] = d.repr(E[p[j]]), ++j;
}
vector<pair<int, int>> subtree_range2 = d.euler_tour();
fenwick_tree tree(N);
vector<int> tour1(N);
for (int i = 0; i < N; ++i)
tour1[subtree_range1[i].first] = i;
vector<pair<int, int>> begin_queries, end_queries;
for (int i = 0; i < Q; ++i)
{
begin_queries.emplace_back(subtree_range1[root1[i]].first, i);
end_queries.emplace_back(subtree_range1[root1[i]].second, i);
}
sort(begin_queries.begin(), begin_queries.end());
sort(end_queries.begin(), end_queries.end());
vector<int> ans(Q);
auto it = begin_queries.begin(), jt = end_queries.begin();
for (int i = 0; i < N; ++i)
{
while (it != begin_queries.end() && it->first == i)
ans[it->second] = -tree.range_sum(subtree_range2[root2[it->second]].first, subtree_range2[root2[it->second]].second), ++it;
tree.update(subtree_range2[tour1[i]].first, 1);
while (jt != end_queries.end() && jt->first == i)
ans[jt->second] += tree.range_sum(subtree_range2[root2[jt->second]].first, subtree_range2[root2[jt->second]].second), ++jt;
}
for (int &x : ans)
x = min(1, x);
return ans;
}
Compilation message
werewolf.cpp: In member function 'std::vector<std::pair<int, int> > dsu::euler_tour()':
werewolf.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < p.size(); ++i)
| ~~^~~~~~~~~~
werewolf.cpp: In member function 'void fenwick_tree::update(int, int)':
werewolf.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | while (i <= t.size())
| ~~^~~~~~~~~~~
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:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while (j < p.size() && L[p[j]] == i)
| ~~^~~~~~~~~~
werewolf.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while (j < p.size() && R[p[j]] == i)
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
4 ms |
980 KB |
Output is correct |
11 |
Correct |
5 ms |
980 KB |
Output is correct |
12 |
Correct |
4 ms |
980 KB |
Output is correct |
13 |
Correct |
4 ms |
1108 KB |
Output is correct |
14 |
Correct |
4 ms |
1108 KB |
Output is correct |
15 |
Correct |
5 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
334 ms |
43020 KB |
Output is correct |
2 |
Correct |
322 ms |
53480 KB |
Output is correct |
3 |
Correct |
327 ms |
52228 KB |
Output is correct |
4 |
Correct |
324 ms |
51608 KB |
Output is correct |
5 |
Correct |
322 ms |
51596 KB |
Output is correct |
6 |
Correct |
334 ms |
51476 KB |
Output is correct |
7 |
Correct |
304 ms |
51524 KB |
Output is correct |
8 |
Correct |
311 ms |
53492 KB |
Output is correct |
9 |
Correct |
285 ms |
52108 KB |
Output is correct |
10 |
Correct |
310 ms |
51636 KB |
Output is correct |
11 |
Correct |
304 ms |
51596 KB |
Output is correct |
12 |
Correct |
312 ms |
51512 KB |
Output is correct |
13 |
Correct |
308 ms |
56308 KB |
Output is correct |
14 |
Correct |
307 ms |
56460 KB |
Output is correct |
15 |
Correct |
306 ms |
56332 KB |
Output is correct |
16 |
Correct |
299 ms |
56332 KB |
Output is correct |
17 |
Correct |
300 ms |
51448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
4 ms |
980 KB |
Output is correct |
11 |
Correct |
5 ms |
980 KB |
Output is correct |
12 |
Correct |
4 ms |
980 KB |
Output is correct |
13 |
Correct |
4 ms |
1108 KB |
Output is correct |
14 |
Correct |
4 ms |
1108 KB |
Output is correct |
15 |
Correct |
5 ms |
1108 KB |
Output is correct |
16 |
Correct |
334 ms |
43020 KB |
Output is correct |
17 |
Correct |
322 ms |
53480 KB |
Output is correct |
18 |
Correct |
327 ms |
52228 KB |
Output is correct |
19 |
Correct |
324 ms |
51608 KB |
Output is correct |
20 |
Correct |
322 ms |
51596 KB |
Output is correct |
21 |
Correct |
334 ms |
51476 KB |
Output is correct |
22 |
Correct |
304 ms |
51524 KB |
Output is correct |
23 |
Correct |
311 ms |
53492 KB |
Output is correct |
24 |
Correct |
285 ms |
52108 KB |
Output is correct |
25 |
Correct |
310 ms |
51636 KB |
Output is correct |
26 |
Correct |
304 ms |
51596 KB |
Output is correct |
27 |
Correct |
312 ms |
51512 KB |
Output is correct |
28 |
Correct |
308 ms |
56308 KB |
Output is correct |
29 |
Correct |
307 ms |
56460 KB |
Output is correct |
30 |
Correct |
306 ms |
56332 KB |
Output is correct |
31 |
Correct |
299 ms |
56332 KB |
Output is correct |
32 |
Correct |
300 ms |
51448 KB |
Output is correct |
33 |
Correct |
381 ms |
51764 KB |
Output is correct |
34 |
Correct |
215 ms |
34468 KB |
Output is correct |
35 |
Correct |
366 ms |
53680 KB |
Output is correct |
36 |
Correct |
353 ms |
51948 KB |
Output is correct |
37 |
Correct |
351 ms |
52012 KB |
Output is correct |
38 |
Correct |
381 ms |
52384 KB |
Output is correct |
39 |
Correct |
330 ms |
59276 KB |
Output is correct |
40 |
Correct |
385 ms |
60436 KB |
Output is correct |
41 |
Correct |
333 ms |
51600 KB |
Output is correct |
42 |
Correct |
296 ms |
51980 KB |
Output is correct |
43 |
Correct |
375 ms |
57612 KB |
Output is correct |
44 |
Correct |
348 ms |
53020 KB |
Output is correct |
45 |
Correct |
328 ms |
59560 KB |
Output is correct |
46 |
Correct |
302 ms |
59276 KB |
Output is correct |
47 |
Correct |
302 ms |
56468 KB |
Output is correct |
48 |
Correct |
309 ms |
56332 KB |
Output is correct |
49 |
Correct |
299 ms |
56460 KB |
Output is correct |
50 |
Correct |
313 ms |
56372 KB |
Output is correct |
51 |
Correct |
377 ms |
60408 KB |
Output is correct |
52 |
Correct |
381 ms |
60356 KB |
Output is correct |