Submission #967522

#	Time	Username	Problem	Language	Result	Execution time	Memory
967522		anton	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	379 ms	42580 KiB

cleaning

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

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