#include <bits/stdc++.h>
#include "Joi.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;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1, S = 60;
#ifdef LOCAL
int Move(int x){ return x; }
void MessageBoard(int a, int b){}
#endif
struct graph{
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);
}
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 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;
if(X == -1) ret = info[x]<<bit;
else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
for(int &u : g[x]) if(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){
sz[x] = 1;
for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
if(sz[x] >= S){
int cnt = 0, v;
good[x] = ++l, is_top[x] = 1;
queue<int> q; q.emplace(x);
while(!q.empty() && cnt < S){
v = q.front(); q.pop(), ++cnt, good[v] = l;
for(int &u : g[v]) if(!good[u]) q.emplace(u);
}
if(X != -1) process(x, good[x], X, 0);
q = queue<int>(), sz[x] = 0;
}
}
};
void Joi(int n, int m, int a[], int b[], ll X, int T){
graph g; g.init(n+1);
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, X);
for(int i = 1; i <= n; ++i) MessageBoard(i-1, g.info[i]);
}
#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;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1, S = 60;
#ifdef LOCAL
int Move(int x){ return x; }
void MessageBoard(int a, int b){}
#endif
struct graph{
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);
}
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)));
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;
if(X == -1) ret = info[x]<<bit;
else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
for(int &u : g[x]) if(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){
sz[x] = 1;
for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
if(sz[x] >= S){
int cnt = 0, v;
good[x] = ++l, is_top[x] = 1;
queue<int> q; q.emplace(x);
while(!q.empty() && cnt < S){
v = q.front(); q.pop(), ++cnt, good[v] = l;
for(int &u : g[v]) if(!good[u]) q.emplace(u);
}
if(X != -1) process(x, good[x], X, 0);
q = queue<int>(), sz[x] = 0;
}
}
};
ll Ioi(int n, int m, int a[], int b[], int p, int val, int T){
graph g; g.init(n+1);
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);
int TOP = g.get_info(p, g.good[p], 0, val);
return g.process(TOP, g.good[TOP], -1, 0);
}
#ifdef LOCAL
void answer(){
}
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
7260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
7260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
7260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
