oj.uz

Submission #417048

# Submission time Handle Problem Language Result Execution time Memory
417048 2021-06-03T11:07:10 Z ACmachine Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 42436 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(hld.pv[j], 0, 1); 
            }
            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 20556 KB Output is correct
2 Correct 581 ms 29856 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 27452 KB Output is correct
2 Correct 195 ms 27548 KB Output is correct
3 Correct 162 ms 29136 KB Output is correct
4 Correct 439 ms 33592 KB Output is correct
5 Correct 559 ms 35900 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 28148 KB Output is correct
2 Correct 177 ms 28144 KB Output is correct
3 Correct 88 ms 37308 KB Output is correct
4 Correct 324 ms 42436 KB Output is correct
5 Correct 66 ms 35704 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 30860 KB Output is correct
2 Correct 207 ms 24772 KB Output is correct
3 Correct 42 ms 22340 KB Output is correct
4 Correct 32 ms 22860 KB Output is correct
5 Correct 38 ms 23392 KB Output is correct
6 Correct 216 ms 26884 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 31112 KB Output is correct
2 Execution timed out 1086 ms 34596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 36908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 581 ms 29856 KB Output is correct
3 Correct 214 ms 27452 KB Output is correct
4 Correct 195 ms 27548 KB Output is correct
5 Correct 162 ms 29136 KB Output is correct
6 Correct 439 ms 33592 KB Output is correct
7 Correct 559 ms 35900 KB Output is correct
8 Correct 159 ms 28148 KB Output is correct
9 Correct 177 ms 28144 KB Output is correct
10 Correct 88 ms 37308 KB Output is correct
11 Correct 324 ms 42436 KB Output is correct
12 Correct 66 ms 35704 KB Output is correct
13 Correct 300 ms 30860 KB Output is correct
14 Correct 207 ms 24772 KB Output is correct
15 Correct 42 ms 22340 KB Output is correct
16 Correct 32 ms 22860 KB Output is correct
17 Correct 38 ms 23392 KB Output is correct
18 Correct 216 ms 26884 KB Output is correct
19 Correct 897 ms 31112 KB Output is correct
20 Execution timed out 1086 ms 34596 KB Time limit exceeded
21 Halted 0 ms 0 KB -