Submission #1295236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295236		veham	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	219 ms	64928 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
#pragma GCC optimize("Ofast") 
#pragma GCC target("avx,avx2,fma")
 
struct Node{
    int ones = 0,twos = 0;
    int l, r;
    bool isupd = 0;
    Node *lc = nullptr, *rc = nullptr;
 
    Node(int l, int r) : l(l), r(r) {
        if(l != r){
            lc = new Node(l,(l+r)/2);
            rc = new Node((l+r)/2+1,r);
        }
    }
 
    void update(){
        if(isupd){
            isupd = 0;
            if(lc){
                lc->isupd = !lc->isupd, rc->isupd = !rc->isupd;
                swap(lc->ones,lc->twos);
                swap(rc->ones,rc->twos);
            }
        }
        if(lc){
            ones = lc->ones + rc->ones;
            twos = lc->twos + rc->twos;
        }
    }
 
    void set_val(int i, int o, int t){
        update();
        if(i < l || i > r) return;
        if(l == r) ones = o, twos = t;
        else lc->set_val(i,o,t),rc->set_val(i,o,t);
        update();
    }
 
    void flip_range(int i, int j){
        update();
        if(j < l || i > r) return;
        if(i <= l && j >= r) swap(ones,twos), isupd = 1;
        else lc->flip_range(i,j), rc->flip_range(i,j);
        update();
    }
 
    int query(int i, int j){
        update();
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return ones + 2*twos;
        return lc->query(i,j) + rc->query(i,j);
    }
};
 
pi operator+(pi a, pi b){
    return {a.first + b.first, a.second + b.second};
}
 
struct Solver{
    int N,R,ho = 1,LC=0;
    vi S,F,H,HN,HT,EP,ISL;
    vvi G,C;
    Node *segt;
 
    void DFS(int v, int prev = -1){
        F[v] = prev;
        if(G[v].size() == 1) EP[v] = ISL[v] = 1, LC++;
        for(int u : G[v]){
            if(u == prev) continue;
            C[v].push_back(u);
            DFS(u,v);
            S[v] += S[u];
            EP[v] += EP[u];
        }
        S[v]++;
        if(!C[v].empty()) H[v] = *max_element(C[v].begin(),C[v].end(),[&](int a, int b){return S[a] < S[b];});
        EP[v] %= 2;
    }
 
    void DFS2(int v, bool is_heavy = 0, int prev = -1){
        HN[v] = ho++;
        if(is_heavy) HT[v] = HT[F[v]];
        else HT[v] = v;
        if(H[v]) DFS2(H[v],1,v);
        for(int u : C[v]){
            if(u == H[v]) continue;
            DFS2(u,0,v);
        }
    }
 
    Solver(int N, int R, vvi G) : N(N), R(R), G(G) {
        S.assign(N+1,0);
        ISL = EP = F = H = HN = HT = S;
        C.assign(N+1,{});
        DFS(R);
        DFS2(R);
        segt = new Node(1,N);
        for(int i = 1;i <= N;i++) segt->set_val(HN[i],EP[i],1-EP[i]);
    }
 
    void flip(int v){
        for(;v != -1;v = F[HT[v]]){
            segt->flip_range(HN[HT[v]],HN[v]);
        }
    }
 
    
    int query(){
        return segt->query(2,N);
    }
};
 
int main(){
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    int N,Q,R,u,v,D;
    cin >> N >> Q;
    vvi G(N+1);
    for(int i = 1;i < N;i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    R = find_if(G.begin(),G.end(),[](vi &V){return V.size() > 1;}) - G.begin();
    Solver S(N,R,G);
 
    vi fl(N+1,-1);
    vi L(1e5);
    int ln;
    for(;Q--;){
        cin >> D;
        ln = 0;
        for(int i = 0;i < D;i++) cin >> L[i];
        for(int i = 0;i < D;i++) if(S.ISL[L[i]] && fl[L[i]] == -1) fl[L[i]] = i, ln++;
        if((S.LC + D - ln)%2){
            cout << -1 << '\n';
        }
        else{
            for(int i = 0;i < D;i++) if(fl[L[i]] != i) S.flip(L[i]);
            cout << (S.query() + D) << '\n';
            for(int i = 0;i < D;i++) if(fl[L[i]] != i) S.flip(L[i]);
        }
        for(int i = 0;i < D;i++) fl[L[i]] = -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