oj.uz

Submission #417071

# Submission time Handle Problem Language Result Execution time Memory
417071 2021-06-03T11:25:47 Z ACmachine Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 949 ms 44100 KB 
#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;
    vector<int> changed;
    REP(i, q){
        changed.clear();
        FOR(j, curr, curr + queries[i], 1){
            if(oleaf[hld.pv[j]]){
                changed.pb(hld.pv[j]);
                oleaf[hld.pv[j]] = false;
                hld.update_path(j, j, 1); 
            }
            else
                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){
            oleaf[v] = true;
            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()){
      |                ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20472 KB Output is correct
2 Correct 448 ms 29780 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 27780 KB Output is correct
2 Correct 210 ms 27772 KB Output is correct
3 Correct 146 ms 29488 KB Output is correct
4 Correct 375 ms 33800 KB Output is correct
5 Correct 422 ms 36368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28220 KB Output is correct
2 Correct 156 ms 28272 KB Output is correct
3 Correct 77 ms 37572 KB Output is correct
4 Correct 303 ms 42564 KB Output is correct
5 Correct 67 ms 35792 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 30980 KB Output is correct
2 Correct 161 ms 24808 KB Output is correct
3 Correct 42 ms 22220 KB Output is correct
4 Correct 33 ms 22828 KB Output is correct
5 Correct 37 ms 23396 KB Output is correct
6 Correct 200 ms 26820 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 31236 KB Output is correct
2 Correct 949 ms 33664 KB Output is correct
3 Correct 760 ms 32048 KB Output is correct
4 Correct 903 ms 34644 KB Output is correct
5 Correct 925 ms 34612 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 37044 KB Output is correct
2 Correct 462 ms 41936 KB Output is correct
3 Correct 525 ms 41284 KB Output is correct
4 Correct 455 ms 42688 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20472 KB Output is correct
2 Correct 448 ms 29780 KB Output is correct
3 Correct 196 ms 27780 KB Output is correct
4 Correct 210 ms 27772 KB Output is correct
5 Correct 146 ms 29488 KB Output is correct
6 Correct 375 ms 33800 KB Output is correct
7 Correct 422 ms 36368 KB Output is correct
8 Correct 156 ms 28220 KB Output is correct
9 Correct 156 ms 28272 KB Output is correct
10 Correct 77 ms 37572 KB Output is correct
11 Correct 303 ms 42564 KB Output is correct
12 Correct 67 ms 35792 KB Output is correct
13 Correct 266 ms 30980 KB Output is correct
14 Correct 161 ms 24808 KB Output is correct
15 Correct 42 ms 22220 KB Output is correct
16 Correct 33 ms 22828 KB Output is correct
17 Correct 37 ms 23396 KB Output is correct
18 Correct 200 ms 26820 KB Output is correct
19 Correct 656 ms 31236 KB Output is correct
20 Correct 949 ms 33664 KB Output is correct
21 Correct 760 ms 32048 KB Output is correct
22 Correct 903 ms 34644 KB Output is correct
23 Correct 925 ms 34612 KB Output is correct
24 Correct 826 ms 37044 KB Output is correct
25 Correct 462 ms 41936 KB Output is correct
26 Correct 525 ms 41284 KB Output is correct
27 Correct 455 ms 42688 KB Output is correct
28 Correct 677 ms 34208 KB Output is correct
29 Correct 459 ms 40988 KB Output is correct
30 Correct 465 ms 37316 KB Output is correct
31 Correct 276 ms 44100 KB Output is correct
32 Correct 912 ms 34608 KB Output is correct
33 Correct 436 ms 38824 KB Output is correct
34 Correct 506 ms 41368 KB Output is correct
35 Correct 491 ms 41168 KB Output is correct