#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int maxn5 = 5e5 + 10;
const int lg = 20;
vector <int> ret, adj[maxn5];
vector <pair<int, pair<int, int>>> req[maxn5];
int n;
void gadd(int);
void grem(int);
void gans(int, int, int);
namespace fen{
int fen[maxn5];
void add(int id, int val){
for(; id < maxn5; id += id & -id)
fen[id] += val;
}
int get(int id){
int ret = 0;
for(; id; id -= id & -id)
ret += fen[id];
return ret;
}
int get(int l, int r){
return get(r) - get(l);
}
}
struct dsu{
int lcpar[lg][maxn5], par[maxn5], ti, st[maxn5], ft[maxn5];
int ver[maxn5], sz[maxn5], newnode, val[maxn5];
pair <int, int> ed[maxn5];
bool mark[maxn5];
dsu(){
memset(lcpar, -1, sizeof lcpar);
memset(par, -1, sizeof par);
memset(mark, false, sizeof mark);
memset(ed, -1, sizeof ed);
ti = 2;
}
int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}
void add(int x){
mark[x] = true;
for(auto u : adj[x]) if(mark[u]){
int a = get_par(u), b = get_par(x);
////cout << u << ' ' << x << ' ' << a << ' ' << b << endl;
if(a == b)
continue;
////cout << "ya merging " << a << ' ' << b << ' ' << newnode << endl;
par[a] = par[b] = lcpar[0][a] = lcpar[0][b] = newnode;
ed[newnode] = {a, b};
val[newnode] = x;
newnode++;
}
}
void dfs_det(int v){
sz[v] = 1;
for(int i = 1; i < lg && lcpar[i - 1][v] != -1; i++)
lcpar[i][v] = lcpar[i - 1][lcpar[i - 1][v]];
st[v] = ++ti;
ver[ti] = v;
if(ed[v].fi == -1){
ft[v] = ti;
return;
}
dfs_det(ed[v].fi);
dfs_det(ed[v].se);
sz[v] += sz[ed[v].fi] + sz[ed[v].se];
if(sz[ed[v].fi] < sz[ed[v].se])
swap(ed[v].fi, ed[v].se);
ft[v] = ti;
}
void query(int id, int l, int r, int s, int e){
int x = s;
for(int i = lg - 1; i >= 0; i--) if(lcpar[i][x] != -1 && val[lcpar[i][x]] >= l)
x = lcpar[i][x];
req[x].pb({id, {r, e}});
}
void inc(int id){
fen::add(st[id], 1);
}
void dec(int id){
fen::add(st[id], -1);
}
void answ(int id, int r, int e){
int x = e;
for(int i = lg - 1; i >= 0; i--) if(lcpar[i][x] != -1 && val[lcpar[i][x]] <= r)
x = lcpar[i][x];
ret[id] = fen::get(st[x], ft[x]) > 0;
}
void gooni(int v, bool keep){
//cout << "allright " << v << ' ' << lcpar[0][v] << ' ' << keep << ' ' << val[v] << endl;
if(ed[v].fi == -1){
gadd(v);
for(auto [id, p] : req[v])
gans(id, p.fi, p.se);
if(!keep)
grem(v);
return;
}
gooni(ed[v].se, false);
gooni(ed[v].fi, true);
gadd(v);
for(int i = st[ed[v].se]; i <= ft[ed[v].se]; i++)
gadd(ver[i]);
for(auto [id, p] : req[v])
gans(id, p.fi, p.se);
if(!keep)
for(int i = st[v]; i <= ft[v]; i++)
grem(ver[i]);
return;
}
} dsu0, dsuN;
void gadd(int v){
if(v >= n)
return;
//cout << "adding " << v << endl;
dsu0.inc(v);
}
void grem(int v){
if(v >= n)
return;
//cout << "removing " << v << endl;
dsu0.dec(v);
}
void gans(int a, int b, int c){
//cout << "going to ans query of " << a << ' ' << b << ' ' << c << endl;
dsu0.answ(a, b, c);
}
std::vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
std::vector<int> s, std::vector<int> e,
std::vector<int> l, std::vector<int> r) {
n = N;
int q = s.size();
for(int i = 0; i < q; i++){
ret.pb(0);
}
int m = x.size();
for(int i = 0; i < m; i++){
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
dsu0.newnode = dsuN.newnode = n;
for(int i = 0; i < n; i++){
////cout << "in dsu 0 " << endl;
dsu0.add(i);
////cout << "in dsu N" << endl;
dsuN.add(n - i - 1);
dsu0.val[i] = dsuN.val[i] = i;
}
dsuN.dfs_det(dsuN.newnode - 1);
dsu0.dfs_det(dsu0.newnode - 1);
////cout << dsu0.lcpar[0][1] << endl;
for(int i = 0; i < q; i++)
dsuN.query(i, l[i], r[i], s[i], e[i]);
dsuN.gooni(dsuN.newnode - 1, true);
return ret;
}
Compilation message
werewolf.cpp: In constructor 'dsu::dsu()':
werewolf.cpp:58:33: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
58 | memset(ed, -1, sizeof ed);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from werewolf.h:3,
from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
211 | struct pair
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
114888 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
114784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
114888 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
114784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
756 ms |
153660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
114888 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
114784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
