oj.uz

Submission #967522

# Submission time Handle Problem Language Result Execution time Memory
967522 2024-04-22T10:27:09 Z anton Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 379 ms 42580 KB 
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

pii combine(pii a, pii b){
    return {a.first +b.first, a.second+b.second};
}
struct SegTree{
    vector<pii> tr;
    vector<int> d;
    int sz= 1;
    
    void init(int len){
        while(sz<len){
            sz*=2;
        }
        tr.resize(2*sz, {0, 0});
        d.resize(2*sz, 0);
    }

    void build(vector<int>&v, int lt, int rt, int t){
        if(lt>=v.size()){
            tr[t] ={0, 0};
        }
        if(lt==rt){
            if(v[lt] ==0){
                tr[t] = {1, 0};
            }
            else{
                tr[t] = {0, 1};
            }
        }
        else{
            int mid = (lt+rt)/2;
            build(v, lt, mid, t*2);
            build(v, mid+1, rt, t*2+1);
            tr[t] = combine(tr[t*2], tr[t*2+1]);
        }
    }

    void push(int id){
        if(d[id]!=0){
            swap(tr[id*2].first, tr[id*2].second);
            swap(tr[id*2+1].first, tr[id*2+1].second);
            d[id] =0;
            d[id*2] ^=1;
            d[id*2+1] ^=1;
        }
    }

    void flip(int l, int r, int lt, int rt, int t){
        
        if(l<= lt && rt<=r){
            d[t]^=1;
            swap(tr[t].first, tr[t].second);
        }
        else if(rt<l || r<lt){
            //cout<<"done "<<endl;
            return;
        }
        else{
            push(t);
            int mid =(lt+rt)/2;
            flip(l, r, lt, mid, t*2);
            flip(l, r, mid+1, rt, t*2+1);
            tr[t] = combine(tr[t*2], tr[t*2+1]);
        }
    }


    pii get(int l, int r, int lt, int rt, int t){
        pii res;
        
        if(rt<l || r<lt){
            res= {0, 0};
        }
        else if(l<= lt && rt<=r){
            
            res= tr[t];
        }
        else{
            push(t);
            int mid = (lt+rt)/2;
            res= combine(get(l, r, lt, mid, t*2), get(l, r, mid+1, rt, t*2+1));
        }
        return res;
    }

    pii change(int l, int r){
        //cout<<"changing on "<<l<<" "<<r<<endl;
        flip(l, r, 0, sz-1, 1);
        return get(l, r, 0, sz-1, 1);
    }
};


struct HLD{

    SegTree seg;
    vector<int> parent, heavy, head, pos, depth, pairdeg;
    vector<vector<int>> adj;
    int cur_pos =0;
    int root =0;

    HLD(int sz, vector<int>& parities, vector<vector<int>> ad, int r){
        root =r;
        parent.resize(sz);
        heavy.resize(sz);
        head.resize(sz);
        pos.resize(sz);
        adj.resize(sz);
        depth.resize(sz);
        pairdeg.resize(sz);
        adj =ad;


        dfs(root, -1, 0);
        decompose(root, root);

        seg.init(sz);

        for(int i = 0; i<sz; i++){
            pairdeg[pos[i]] = parities[i];
        }
        seg.build(pairdeg, 0, seg.sz-1, 1);
    }

    int dfs(int u, int a, int dp){
        depth[u] =dp;
        parent[u] = a;
        int sz= 1;
        int id= -1, maxsz= 0;
        for(auto v: adj[u]){
            if(v!=a){
                int res= dfs(v, u, dp+1);
                if(res>maxsz){
                    id = v;
                    maxsz =res;
                }
                sz+=res;
            }
        }
        heavy[u] = id;
        return sz;
    }

    void decompose(int u, int h){
        head[u] = h;
        pos[u] = cur_pos++;

        if(heavy[u]!=-1){
            decompose(heavy[u], h);
        }
        for(auto v: adj[u]){
            if(v!=heavy[u] && v!=parent[u]){
                decompose(v, v);
            }
        }

    };

    pii change_upwards(int u){
        pii res ={0, 0};
        while(head[u] != root){
            //cout<<"c "<<head[u]<<" "<<u<<endl;
            res = combine(res, seg.change(pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        
        //cout<<"c "<<root    <<" "<<u<<endl;
        res = combine(res, seg.change(pos[root], pos[u]));
        //cout<<"cres "<<res.first<<" "<<res.second<<endl;
        return res;
    }
};

const int MAX_N = 100000;

vector<vector<int>> adj;
vector<int> parity;
vector<int> cost = {2, 1};

int total_cost= 0;

int count_leaves(int u, int a){
    int s= 0;
    for(auto v: adj[u]){
        if(v!=a){
            s+=count_leaves(v, u);
        }
    }
    if(s==0){
        s=1;
    }
    total_cost+= cost[s%2];
    
    //cout<<u+1<<" "<<s<<endl;
    parity[u] = s%2;
    return s;
}


signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, k;
    cin>>n>>k;
    adj.resize(n);
    parity.resize(n);

    int node = 0;
    int deg= 0;

    for(int i = 0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);

        if(adj[a].size()>deg){
            node =a;
            deg = adj[a].size();
        }
        if(adj[b].size()>deg){
            node =b;
            deg = adj[b].size();
        }
    }


    int r= count_leaves(node, -1);
    HLD hld(n, parity, adj, node);
    //pii v= hld.seg.get(0, 0, 0, hld.seg.sz-1, 1);
    //cout<<v.first<<" "<<v.second<<endl;

    for(int i = 0; i<k; i++){
        int d;
        cin>>d;
        vector<int> pos(d);
        for(int i = 0; i<d; i++){
            cin>>pos[i];
            pos[i]--;
        }

        for(auto e: pos){
            adj[e].push_back(-1);
            if(adj[e].size()>2){
                pii new_val =hld.change_upwards(e);
                total_cost -= new_val.second * cost[0] + new_val.first * cost[1];
                total_cost += new_val.first * cost[0] + new_val.second * cost[1];
            }
        }

        pii v= hld.seg.get(0, 0, 0, hld.seg.sz-1, 1);
        //cout<<v.first<<" "<<v.second<<endl;
        if(hld.seg.get(0, 0, 0, hld.seg.sz-1, 1) != pair<int, int>({1, 0})){
            cout<<-1<<endl;
        }
        else{
            cout<<total_cost-2 +d<<endl;
        }

        for(auto e: pos){
            if(adj[e].size()>2){
                pii new_val =hld.change_upwards(e);
                total_cost -= new_val.second * cost[0] + new_val.first * cost[1];
                total_cost += new_val.first * cost[0] + new_val.second * cost[1];
            }
            adj[e].pop_back();
        }
        //cout<<"baseline: "<<total_cost-2<<endl;
    }
}

Compilation message

cleaning.cpp: In member function 'void SegTree::build(std::vector<int>&, int, int, int)':
cleaning.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(lt>=v.size()){
      |            ~~^~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:222:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  222 |         if(adj[a].size()>deg){
      |            ~~~~~~~~~~~~~^~~~
cleaning.cpp:226:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  226 |         if(adj[b].size()>deg){
      |            ~~~~~~~~~~~~~^~~~
cleaning.cpp:256:13: warning: variable 'v' set but not used [-Wunused-but-set-variable]
  256 |         pii v= hld.seg.get(0, 0, 0, hld.seg.sz-1, 1);
      |             ^
cleaning.cpp:233:9: warning: unused variable 'r' [-Wunused-variable]
  233 |     int r= count_leaves(node, -1);
      |         ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 158 ms 5388 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2132 KB Output is correct
2 Correct 67 ms 2132 KB Output is correct
3 Correct 39 ms 24524 KB Output is correct
4 Correct 91 ms 18392 KB Output is correct
5 Correct 93 ms 24776 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3640 KB Output is correct
2 Correct 58 ms 3636 KB Output is correct
3 Correct 59 ms 36236 KB Output is correct
4 Correct 155 ms 36944 KB Output is correct
5 Correct 54 ms 42580 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 7180 KB Output is correct
2 Correct 49 ms 5488 KB Output is correct
3 Correct 10 ms 5208 KB Output is correct
4 Correct 13 ms 7004 KB Output is correct
5 Correct 13 ms 7000 KB Output is correct
6 Correct 64 ms 6492 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 15220 KB Output is correct
2 Correct 270 ms 15344 KB Output is correct
3 Correct 230 ms 8028 KB Output is correct
4 Correct 272 ms 15340 KB Output is correct
5 Correct 319 ms 15376 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 24268 KB Output is correct
2 Correct 273 ms 35668 KB Output is correct
3 Correct 299 ms 35160 KB Output is correct
4 Correct 313 ms 31692 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 158 ms 5388 KB Output is correct
3 Correct 67 ms 2132 KB Output is correct
4 Correct 67 ms 2132 KB Output is correct
5 Correct 39 ms 24524 KB Output is correct
6 Correct 91 ms 18392 KB Output is correct
7 Correct 93 ms 24776 KB Output is correct
8 Correct 65 ms 3640 KB Output is correct
9 Correct 58 ms 3636 KB Output is correct
10 Correct 59 ms 36236 KB Output is correct
11 Correct 155 ms 36944 KB Output is correct
12 Correct 54 ms 42580 KB Output is correct
13 Correct 107 ms 7180 KB Output is correct
14 Correct 49 ms 5488 KB Output is correct
15 Correct 10 ms 5208 KB Output is correct
16 Correct 13 ms 7004 KB Output is correct
17 Correct 13 ms 7000 KB Output is correct
18 Correct 64 ms 6492 KB Output is correct
19 Correct 265 ms 15220 KB Output is correct
20 Correct 270 ms 15344 KB Output is correct
21 Correct 230 ms 8028 KB Output is correct
22 Correct 272 ms 15340 KB Output is correct
23 Correct 319 ms 15376 KB Output is correct
24 Correct 379 ms 24268 KB Output is correct
25 Correct 273 ms 35668 KB Output is correct
26 Correct 299 ms 35160 KB Output is correct
27 Correct 313 ms 31692 KB Output is correct
28 Correct 199 ms 14560 KB Output is correct
29 Correct 192 ms 34896 KB Output is correct
30 Correct 97 ms 24776 KB Output is correct
31 Correct 139 ms 41624 KB Output is correct
32 Correct 266 ms 15440 KB Output is correct
33 Correct 195 ms 26192 KB Output is correct
34 Correct 193 ms 35276 KB Output is correct
35 Correct 205 ms 31060 KB Output is correct