#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
const int LOGN = 19;
vector<int> adj[N], ans, tr[2][N], tour[2];
vector<array<int, 2>> sweepline[N];
int n, q, s[N], e[N], l[N], r[N];
int st[2][N], en[2][N], par[2][N], lca[LOGN][N], pos[N];
struct DSU{
int sz[N], p[N], head[N];
DSU(){}
void init(){
for(int i = 0; i < n; ++i)
sz[i] = 1, p[i] = i, head[i] = i;
}
int get_p(int x){
if(x == p[x]) return x;
return p[x] = get_p(p[x]);
}
bool unite(int a, int b, int idx){
a = get_p(a), b = get_p(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
if(!idx) head[a] = max(head[a], head[b]);
else head[a] = min(head[a], head[b]);
return true;
}
} dsu;
struct Fenwick{
int a[N];
Fenwick(){}
void update(int i){
for(++i; i < N; i += i&-i)
a[i] += 1;
}
int query(int i){
int ans = 0;
for(++i; i >= 1; i -= i&-i)
ans += a[i];
return ans;
}
int query(int l, int r){
return query(r) - query(l - 1);
}
} f;
void euler_tour(int u, int idx){
st[idx][u] = tour[idx].size();
tour[idx].push_back(u);
for(int to: tr[idx][u])
euler_tour(to, idx);
en[idx][u] = tour[idx].size() - 1;
}
void do_lca(int idx){
for(int i = 0; i < n; ++i)
lca[0][i] = par[idx][i];
for(int j = 1; j < LOGN; ++j)
for(int i = 0; i < n; ++i)
lca[j][i] = lca[j - 1][lca[j - 1][i]];
for(int i = 0; i < q; ++i){
if(idx == 0){
for(int j = LOGN - 1; j >= 0; --j)
if(lca[j][s[i]] <= r[i])
e[i] = lca[j][e[i]];
}
else{
//cout << s[i] << " before" << endl;
for(int j = LOGN - 1; j >= 0; --j){
//cout << lca[j][s[i]] << " lca" << endl;
if(lca[j][s[i]] >= l[i])
s[i] = lca[j][s[i]];
}
//cout << s[i] << " after" << endl;
}
}
}
vector<int> check_validity(int _N, vector<int> _X, vector<int> _Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R){
n = _N, q = _S.size();
ans.resize(q, 0);
for(int i = 0; i < _X.size(); ++i){
adj[_X[i]].push_back(_Y[i]);
adj[_Y[i]].push_back(_X[i]);
}
for(int i = 0; i < q; ++i)
s[i] = _S[i], e[i] = _E[i], l[i] = _L[i], r[i] = _R[i];
dsu.init();
for(int i = 0; i < n; ++i){
for(int to: adj[i]){
int x = dsu.head[dsu.get_p(to)];
if(to < i && dsu.unite(to, i, 0)){
tr[0][i].push_back(x);
par[0][x] = i;
//cout << "edge0 " << i << " -> " << x << endl;
}
}
}
par[0][n - 1] = n - 1;
dsu.init();
for(int i = n - 1; i >= 0; --i){
for(int to: adj[i]){
int x = dsu.head[dsu.get_p(to)];
if(to > i && dsu.unite(to, i, 1)){
tr[1][i].push_back(x);
par[1][x] = i;
//cout << "edge1 " << i << " -> " << x << endl;
}
}
}
par[1][0] = 0;
//cout << "done with dsu" << endl;
euler_tour(n - 1, 0);
euler_tour(0, 1);
//cout << "done with euler_tour" << endl;
do_lca(0);
do_lca(1);
//cout << "done with lca" << endl;
//for(int i = 0; i < q; ++i)
// cout << s[i] << " " << e[i] << " query " << i << endl;
for(int i = 0; i < q; ++i){
//cout << i << " sweepline" << endl;
sweepline[st[1][s[i]]].push_back({0, i});
sweepline[en[1][s[i]] + 1].push_back({1, i});
}
for(int i = 0; i < n; ++i){
//cout << " tour " << tour[0][i] << endl;
pos[tour[0][i]] = i;
}
for(int i = 0; i <= n; ++i){
//cout << i << endl;
for(auto [type, idx]: sweepline[i]){
//cout << type << " " << idx << " type idx" << endl;
if(!type) ans[idx] = f.query(st[0][e[idx]], en[0][e[idx]]);
else ans[idx] = !!(f.query(st[0][e[idx]], en[0][e[idx]]) - ans[idx]);
}
if(i != n) f.update(pos[tour[1][i]]);
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
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:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < _X.size(); ++i){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
746 ms |
87520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
