#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FOR(i, n, 0, 1)
#define pb push_back
typedef long long ll;
struct node{
int even = 0, odd = 0;
int flag = 0;
void apply(int l, int r, int val){
swap(even, odd);
flag ^= 1;
}
};
struct segtree{
node comb(node const &a, node const &b){
node res;
res.even = a.even + b.even;
res.odd = a.odd + b.odd;
return res;
}
void push(int l, int r, int v){
if(tree[v].flag == 0) return;
tree[v<<1].apply(l, r, tree[v].flag);
tree[v<<1|1].apply(l, r, tree[v].flag);
tree[v].flag = 0;
}
vector<node> tree;
int n;
segtree(){}
segtree(int _n){
n = 1; while(n < _n) n*= 2;
tree.resize(2 * n);
}
void build(vector<node> &init){
REP(i, n){
if(i < init.size()){
tree[i + n] = init[i];
}
}
FORD(i, n - 1, 1, 1){
tree[i] = comb(tree[i << 1], tree[i << 1|1]);
}
}
node query(int l, int r){return query0(l, r, 0, n, 1);}
node query0(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r)
return tree[v];
push(beg, end, v);
int mid = (beg + end) >> 1;
node res;
if(beg >= r || mid <= l) res = query0(l, r, mid, end, v<<1|1);
else if(mid >= r || end <= l) res = query0(l, r, beg, mid, v<<1);
else res = comb(query0(l, r, beg, mid, v<<1), query0(l, r, mid, end, v<<1|1));
return res;
}
void upd(int l, int r, int val){ upd0(l, r, 0, n, 1, val); }
void upd0(int l, int r, int beg, int end, int v, int val){
if(beg >= r || end <= l)
return;
if(beg >= l && end <= r){
tree[v].apply(beg, end, val);
return;
}
push(beg, end, v);
int mid = (beg + end) >> 1;
upd0(l, r, beg, mid, v<<1, val);
upd0(l, r, mid, end, v<<1|1, val);
tree[v] = comb(tree[v<<1], tree[v<<1|1]);
}
};
struct heavy_light{
vector<vector<int>> g;
int n;
vector<int> pv, sz, in, out, depth, nxt;
segtree st;
int timer = 0;
heavy_light(vector<vector<int>> &_g) : g(_g){
n = g.size();
st = segtree(n);
pv.resize(n, -1);
sz.resize(n);
in.resize(n);
out.resize(n);
depth.resize(n, 0);
nxt.resize(n);
function<void(int, int)> dfs_sz = [&](int v, int p){
sz[v] = 1;
pv[v] = p;
if(p != -1)
depth[v] = depth[p] + 1;
for(int &x : g[v]){
if(x == p) continue;
dfs_sz(x, v);
sz[v] += sz[x];
if(sz[x] > sz[g[v][0]])
swap(x, g[v][0]);
}
};
dfs_sz(0, -1);
function<void(int)> dfs_hld = [&](int v){
in[v] = timer++;
for(int x : g[v]){
if(x == pv[v]) continue;
nxt[x] = (x == g[v][0] ? nxt[v] : x);
dfs_hld(x);
}
out[v] = timer;
};
dfs_hld(0);
}
node query_path(int u, int v){
node ans;
for(;nxt[u] != nxt[v]; v = pv[nxt[v]]){
if(depth[nxt[u]] > depth[nxt[v]]) swap(u, v);
ans = st.comb(ans, st.query(in[nxt[v]], in[v] + 1));
}
if(depth[u] > depth[v]) swap(u, v);
ans = st.comb(ans, st.query(in[u], in[v] + 1));
return ans;
}
void update_path(int u, int v, int val){
for(;nxt[u] != nxt[v]; v = pv[nxt[v]]){
if(depth[nxt[u]] > depth[nxt[v]]) swap(u, v);
st.upd(in[nxt[v]], in[v] + 1, val);
}
if(depth[u] > depth[v])swap(u, v);
st.upd(in[u], in[v] + 1, val);
}
};
const int mx = 200005;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<vector<int>> g(mx);
vector<int> queries(q);
REP(i, n - 1){
int u, v;
cin >> u >> v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
}
int nn = n;
vector<int> ans(q, 0);
REP(i, q){
int d;
cin >> d;
queries[i] = d;
REP(j, d){
int a;
cin >> a;
a--;
g[a].pb(nn);
g[nn].pb(a);
nn++;
}
}
heavy_light hld(g);
vector<node> init(nn);
REP(i, nn){
init[i].even = 1;
}
hld.st.build(init);
vector<bool> oleaf(nn, false);
int num_leaves = 0;
REP(i, n){
int cnt = 0;
for(int x : g[i]){
if(x < n)
cnt++;
}
if(cnt == 1){
oleaf[i] = true;
num_leaves++;
hld.update_path(i, 0, 1);
}
}
int curr = n;
set<int> changed;
REP(i, q){
FOR(j, curr, curr + queries[i], 1){
if(oleaf[hld.pv[j]] && changed.find(hld.pv[j]) == changed.end()){
hld.update_path(hld.pv[j], 0, 1);
changed.insert(hld.pv[j]);
}
hld.update_path(j, 0, 1);
}
auto no = hld.st.query(0, nn);
auto no2 = hld.st.query(0, 1);
no.odd -= no2.odd;
no.even -= no2.even;
no.even -= (nn - (n + queries[i]));
ans[i] = no.even * 2 + no.odd;
if((num_leaves - (int)changed.size() + queries[i]) % 2 == 1)
ans[i] = -1;
FOR(j, curr, curr + queries[i], 1){
hld.update_path(j, 0, 1);
}
for(int v : changed){
hld.update_path(v, 0, 1);
}
curr += queries[i];
}
REP(i, q){
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
cleaning.cpp: In member function 'void segtree::build(std::vector<node>&)':
cleaning.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if(i < init.size()){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
20556 KB |
Output is correct |
| 2 |
Execution timed out |
1081 ms |
30508 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
27972 KB |
Output is correct |
| 2 |
Correct |
264 ms |
27972 KB |
Output is correct |
| 3 |
Correct |
150 ms |
30128 KB |
Output is correct |
| 4 |
Correct |
499 ms |
36536 KB |
Output is correct |
| 5 |
Correct |
563 ms |
39604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
28580 KB |
Output is correct |
| 2 |
Correct |
154 ms |
28456 KB |
Output is correct |
| 3 |
Correct |
79 ms |
38544 KB |
Output is correct |
| 4 |
Correct |
330 ms |
44016 KB |
Output is correct |
| 5 |
Correct |
72 ms |
36700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
32008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
32128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
38472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
20556 KB |
Output is correct |
| 2 |
Execution timed out |
1081 ms |
30508 KB |
Time limit exceeded |
