Submission #417044

#	Time	Username	Problem	Language	Result	Execution time	Memory
417044		ACmachine	Spring cleaning (CEOI20_cleaning)	C++17	18 / 100	1094 ms	44016 KiB

cleaning

#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 (stderr)

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30