#include "Joi.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, d[N], cnt, par[N], f[N];
ll ans;
vector<int> adj[N];
bool vis[N], ok;
set<pii> leaf;
set<int> st[N], cur, res;
void dfs(int u, int p = -1)
{
vis[u] = true;
if(cnt < M)d[u] = cnt++;
else
{
auto it = leaf.begin();
if(d[par[u]] == (*it).se)++it;
int v = (*it).se;
cur.erase(b[v]);
d[u] = v;
leaf.erase(it);
for(int x: st[v])
{
leaf.erase({(int)st[x].size(), x});
st[x].erase(v);
leaf.insert({(int)st[x].size(), x});
}
st[v].clear();
}
if(u == 0)leaf.insert({0, d[u]});
else leaf.insert({1, d[u]});
b[d[u]] = u;
cur.insert(u);
if(p == u)ok = true;
if(ok && cnt == M)
{
res = cur;
ok = false;
}
if(u != 0)
{
int v = d[par[u]];
leaf.erase({(int)st[v].size(), v});
st[v].insert(d[u]);
st[d[u]].insert(v);
leaf.insert({(int)st[v].size(), v});
}
//cout << u <<" "<<d[u]<<'\n';
for(int v: adj[u])
{
if(vis[v])continue;
par[v] = u;
dfs(v, p);
}
}
void Joi(int n, int m, int A[], int B[], ll x, int T)
{
for(int i = 0; i < n; i ++)
{
st[i].clear();
adj[i].clear();
}
leaf.clear();
res.clear();
cur.clear();
cnt = 0;
for(int i = 0; i < m; i ++)
{
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
fill_n(d, n, -1);
fill_n(par, n, -1);
fill_n(vis, n, 0);
dfs(0);
for(int i = 0; i < n; i ++)
{
assert(d[i] != -1);
MessageBoard(i, (x>>d[i]&1));
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, d[N], cnt, par[N], f[N];
ll ans;
vector<int> adj[N];
bool vis[N], ok;
set<pii> leaf;
set<int> st[N], cur, res;
bool check(set<int> st, int n)
{
DSU dsu(n);
for(int u: st)
{
for(int v: adj[u])if(st.find(v) != st.end())dsu.hop(u, v);
}
return dsu.m == M-1;
}
void dfs(int u, int p = -1)
{
vis[u] = true;
if(cnt < M)d[u] = cnt++;
else
{
auto it = leaf.begin();
if(d[par[u]] == (*it).se)++it;
int v = (*it).se;
assert(st[v].size() == 1);
cur.erase(b[v]);
d[u] = v;
leaf.erase(it);
for(int x: st[v])
{
leaf.erase({(int)st[x].size(), x});
st[x].erase(v);
leaf.insert({(int)st[x].size(), x});
}
st[v].clear();
}
if(u == 0)leaf.insert({0, d[u]});
else leaf.insert({1, d[u]});
b[d[u]] = u;
cur.insert(u);
if(p != -1 && vis[p] && cnt == M && res.empty())res = cur;
if(u != 0)
{
int v = d[par[u]];
leaf.erase({(int)st[v].size(), v});
st[v].insert(d[u]);
st[d[u]].insert(v);
leaf.insert({(int)st[v].size(), v});
}
//cout << u <<" "<<d[u]<<'\n';
for(int v: adj[u])
{
if(vis[v])continue;
par[v] = u;
dfs(v, p);
}
}
void cal(int u)
{
//cout << u <<" "<<d[u]<<" "<<a[d[u]]<<'\n';
for(int v: adj[u])
{
if(res.find(v) == res.end())continue;
a[d[v]] = Move(v);
res.erase(v);
cal(v);
Move(u);
}
}
struct DSU
{
int n, m;
vector<int> lab;
DSU(int _n)
{
n = _n;
m = 0;
lab.resize(n, -1);
}
int findp(int u)
{
return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(int u, int v)
{
u = findp(u);
v = findp(v);
if(u == v)return;
if(lab[u] > lab[v])swap(u, v);
lab[u] += lab[v];
lab[v] = u;
++m;
}
};
ll Ioi(int n, int m, int A[], int B[], int P, int V, int T)
{
for(int i = 0; i < n; i ++)
{
st[i].clear();
adj[i].clear();
}
res.clear();
cur.clear();
leaf.clear();
cnt = 0;
for(int i = 0; i < m; i ++)
{
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
fill_n(d, n, -1);
fill_n(par, n, -1);
fill_n(vis, n, 0);
dfs(0, P);
fill_n(a, M, -1);
a[d[P]] = V;
res.erase(P);
cal(P);
//assert(res.empty());
ll res = 0;
for(int i = 0; i < M; i ++)
{
//cout << a[i] <<" "<<i<<'\n';
//assert(a[i] != -1);
if(a[i])
res |= (1ll<<i);
}
return res;
}
Compilation message
Ioi.cpp: In function 'bool check(std::set<int>, int)':
Ioi.cpp:25:5: error: 'DSU' was not declared in this scope
25 | DSU dsu(n);
| ^~~
Ioi.cpp:28:53: error: 'dsu' was not declared in this scope
28 | for(int v: adj[u])if(st.find(v) != st.end())dsu.hop(u, v);
| ^~~
Ioi.cpp:30:12: error: 'dsu' was not declared in this scope
30 | return dsu.m == M-1;
| ^~~
