#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)
{
pii change;
set<int> stchange;
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]);
change.fi = v;
change.se = b[v];
d[u] = v;
leaf.erase(it);
stchange = st[v];
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({1, d[u]});
else leaf.insert({0, d[u]});
b[d[u]] = u;
cur.insert(u);
if(p != -1 && vis[p] && cnt == M)
{
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);
}
if(!stchange.empty())
{
cur.erase(u);
cur.insert(change.se);
leaf.erase({1, d[u]});
leaf.insert({1, change.fi});
b[change.fi] = change.se;
for(int x: stchange)
{
leaf.erase({(int)st[x].size(), x});
st[x].insert(change.fi);
leaf.insert({(int)st[x].size(), x});
}
st[change.fi] = stchange;
int v = d[par[u]];
leaf.erase({(int)st[v].size(), v});
st[v].erase(d[u]);
st[d[u]].erase(v);
leaf.insert({(int)st[v].size(), v});
}
}
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 ++)
{
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;
void dfs(int u, int p = -1)
{
pii change;
set<int> stchange;
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]);
change.fi = v;
change.se = b[v];
d[u] = v;
leaf.erase(it);
stchange = st[v];
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({1, d[u]});
else leaf.insert({0, d[u]});
b[d[u]] = u;
cur.insert(u);
if(p == u)ok = true;
if(p != -1 && vis[p] && cnt == M)
{
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);
}
if(!stchange.empty())
{
cur.erase(u);
cur.insert(change.se);
leaf.erase({1, d[u]});
leaf.insert({1, change.fi});
b[change.fi] = change.se;
for(int x: stchange)
{
leaf.erase({(int)st[x].size(), x});
st[x].insert(change.fi);
leaf.insert({(int)st[x].size(), x});
}
st[change.fi] = stchange;
int v = d[par[u]];
leaf.erase({(int)st[v].size(), v});
st[v].erase(d[u]);
st[d[u]].erase(v);
leaf.insert({(int)st[v].size(), v});
}
}
void cal(int u)
{
//cout << u <<" "<<d[u]<<" "<<a[d[u]]<<'\n';
for(int v: adj[u])
{
if(res.find(v) == res.end())continue;
if(a[d[v]] == -1)
{
a[d[v]] = Move(v);
res.erase(v);
cal(v);
Move(u);
}
}
}
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;
ok = false;
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);
res.erase(P);
a[d[P]] = V;
cal(P);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28936 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
43572 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
51524 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
43568 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
91 ms |
51476 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
51448 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
