#include <bits/stdc++.h>
#include "Ioi.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend();
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#ifdef LOCAL
int Move(int x){ return x; }
void MessageBoard(int a, int b){}
#endif
struct gph{
vv<vv<int>> bg, g;
vv<int> vis, good, is_top, sz;
vv<ll> info;
void init(int n){
bg.resize(n+1), g.resize(n+1), vis.resize(n+1), good.resize(n+1, 0), info.resize(n+1, 0), sz.resize(n+1), is_top.resize(n+1);
}
void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); }
void add_edge(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); }
void get_tree(int x){
vis[x] = 1;
for(int &u : bg[x]) if(!vis[u]) add_edge(x, u), get_tree(u);
}
vv<int> find_closest_group(int x){ // zwroci wektor tych, po ktorych musze sie poruszac, by dojsc do najblizszej grupy
fill(all(vis), 0);
int v;
vv<int> ret;
queue<int> q; q.emplace(x); vis[x] = -1;
while(!q.empty()){
v = q.front(); q.pop();
if(good[v]){
while(vis[v] != -1) ret.emplace_back(v), v = vis[v];
break;
}
for(int &u : g[v]) if(!vis[u]) vis[u] = v, q.emplace(u);
}
q = queue<int>();
return ret;
}
int get_info(int x, int gr, int par, int val){
int ret = is_top[x] ? x : 0;
info[x] = val;
for(int &u : g[x]) if(u != par && good[u] == gr) ret = max(ret, get_info(u, gr, x, Move(u-1)));
if(par) Move(par-1);
return ret;
}
int bit = 0;
ll process(int x, int gr, ll X, int par){ // X -1 = zwroc, w przeciwnym wypadku zakoduj TRZEBA PAMIETAC, BY POSORTOWAC WEKTOR SASIEDZTWA
if(is_top[x]) bit = 0;
ll ret = 0;
//~ printf("%d: %lld %d\n", x, info[x], bit);
if(X == -1) ret = info[x]<<bit;
else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
for(int &u : g[x]) if(good[u] == gr && u != par) ++bit, ret += process(u, gr, X, x);
return ret;
}
int l = 0; // ktora grupa
void get_groups(int x, int par, int X){
//~ printf("%d\n", x);
sz[x] = 1;
for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
if(sz[x] >= 60){
int cnt = 0, v, p;
good[x] = ++l, is_top[x] = 1;
queue<pii> q; q.emplace(x, par);
while(!q.empty() && cnt < 60){
v = q.front().fi, p = q.front().se; q.pop(), ++cnt, good[v] = l;
for(int &u : g[v]) if(u != p && !good[u]) q.emplace(u, v);
}
if(X != -1) process(x, good[x], X, 0);
q = queue<pii>(), sz[x] = 0;
}
}
};
ll Ioi(int n, int m, int a[], int b[], int p, int val, int T){
gph g; g.init(n+1); ++p;
for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
g.get_tree(31);
for(int i = 1; i <= n; ++i) sort(all(g.g[i]));
g.get_groups(31, 0, -1);
vv<int> path = g.find_closest_group(p);
while(!path.empty()) p = path.back(), path.pop_back(), val = Move(p-1);
int TOP = g.get_info(p, g.good[p], 0, val);
ll ret = g.process(TOP, g.good[TOP], -1, 0);
return ret;
return 0;
}
#ifdef LOCAL
void answer(){
}
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
#endif
#include <bits/stdc++.h>
#include "Ioi.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend();
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct gph{
vv<vv<int>> bg, g;
vv<int> vis, good, is_top, sz;
vv<ll> info;
void init(int n){
bg.resize(n+1), g.resize(n+1), vis.resize(n+1), good.resize(n+1, 0), info.resize(n+1, 0), sz.resize(n+1), is_top.resize(n+1);
}
void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); }
void add_edge(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); }
void get_tree(int x){
vis[x] = 1;
for(int &u : bg[x]) if(!vis[u]) add_edge(x, u), get_tree(u);
}
vv<int> find_closest_group(int x){ // zwroci wektor tych, po ktorych musze sie poruszac, by dojsc do najblizszej grupy
fill(all(vis), 0);
int v;
vv<int> ret;
queue<int> q; q.emplace(x); vis[x] = 0;
while(!q.empty()){
v = q.front(); q.pop();
if(good[v]){
while(vis[v]) ret.emplace_back(v), v = vis[v];
break;
}
for(int &u : g[v]) if(!vis[u]) vis[u] = x, q.emplace(u);
}
q = queue<int>();
return ret;
}
int get_info(int x, int gr, int par, int val){
int ret = is_top[x] ? x : 0;
info[x] = val;
for(int &u : g[x]) if(u != par && good[u] == gr) ret = max(ret, get_info(u, gr, x, Move(u-1)));
if(par) Move(par-1);
return ret;
}
int bit = 0;
ll process(int x, int gr, ll X, int par){ // X -1 = zwroc, w przeciwnym wypadku zakoduj TRZEBA PAMIETAC, BY POSORTOWAC WEKTOR SASIEDZTWA
if(is_top[x]) bit = 0;
ll ret = 0;
//~ printf("%d: %lld %d\n", x, info[x], bit);
if(X == -1) ret = info[x]<<bit;
else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
for(int &u : g[x]) if(good[u] == gr && u != par) ++bit, ret += process(u, gr, X, x);
return ret;
}
int l = 0; // ktora grupa
void get_groups(int x, int par, int X){
//~ printf("%d\n", x);
sz[x] = 1;
for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
if(sz[x] >= 60){
int cnt = 0, v, p;
good[x] = ++l, is_top[x] = 1;
queue<pii> q; q.emplace(x, par);
while(!q.empty() && cnt < 60){
v = q.front().fi, p = q.front().se; q.pop(), ++cnt, good[v] = l;
for(int &u : g[v]) if(u != p && !good[u]) q.emplace(u, v);
}
if(X != -1) process(x, good[x], X, 0);
q = queue<pii>(), sz[x] = 0;
}
}
};
ll Ioi(int n, int m, int a[], int b[], int p, int val, int T){
/*gph g; g.init(n+1); ++p;
for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
g.get_tree(1);
for(int i = 1; i <= n; ++i) sort(all(g.g[i]));
g.get_groups(1, 0, -1);
vv<int> path = g.find_closest_group(p);
while(!path.empty()) p = path.back(), path.pop_back(), val = Move(p-1);
int TOP = g.get_info(p, g.good[p], 0, val);
ll ret = g.process(TOP, g.good[TOP], -1, 0);
return ret;*/
return 0;
}
#ifdef LOCAL
void answer(){
}
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
#endif
Compilation message
Joi.cpp: In member function 'int gph::get_info(int, int, int, int)':
Joi.cpp:49:88: error: 'Move' was not declared in this scope
49 | for(int &u : g[x]) if(u != par && good[u] == gr) ret = max(ret, get_info(u, gr, x, Move(u-1)));
| ^~~~
Joi.cpp:50:13: error: 'Move' was not declared in this scope
50 | if(par) Move(par-1);
| ^~~~
Joi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Joi.cpp:88:64: error: 'Move' was not declared in this scope
88 | while(!path.empty()) p = path.back(), path.pop_back(), val = Move(p-1);
| ^~~~
