Submission #1358229

#TimeUsernameProblemLanguageResultExecution timeMemory
1358229sanoSpring cleaning (CEOI20_cleaning)C++20
0 / 100
1094 ms20564 KiB
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <unordered_map>
#include <queue>
#define NEK 1000000000
#define ll long long
#define vec vector
#define For(i, n) for(int i = 0; i < n; i++)
#define ld long double
#define pii pair<int, int>
#define ff first
#define int ll
#define ss second
#define ld long double
#define mod 1000000007
#define sig 0.000001
#define all(x) x.begin(), x.end()
using namespace std;


class intervalac{
    vec<int> in, lp, l, r;
    int n;
    void apply(int s){
        in[s] = 3 * (r[s] - l[s] + 1) - in[s];
        lp[s] = 1 - lp[s];
        return;
    }
    void propagate(int s){
        if(lp[s] == 0) return;
        apply(s*2);
        apply(s*2 + 1);
        lp[s] = 0;
        return;
    }
    void update(int s){
        in[s] = in[s*2] + in[s*2 + 1];
        return;
    }
public:
    intervalac(int vel){
        n = 1;
        while(n < vel) n*= 2;
        in.resize(2*n, 0);
        l.resize(2*n); r.resize(2*n);
        lp.resize(2*n, 0);
        For(i, n){
            l[i+n] = r[i+n] = i;
        }
        for(int i = n-1; i >= 1; i--){
            l[i] = l[i*2];
            r[i] = r[i*2 + 1];
        }
    }
    void zmen(int a, int b){
        a+=n;
        in[a] = b;
        a/=2;
        while(a){
            update(a);
            a/=2;
        }
        return;
    }
    int daj(int a, int b, int s = 1){
        if(l[s] > b || r[s] < a) return 0;
        if(a <= l[s] && r[s] <= b) {
            int vel = r[s] - l[s] + 1;
            int pv = in[s];
            apply(s);
            return 3 * vel - 2 * pv;
        }
        propagate(s);
        update(s);
        return daj(a, b, s*2) + daj(a, b, s*2 + 1);
    }
};





vec<vec<int>> g;
vec<int> vrst;
vec<int> par;
vec<int> o;
vec<int> nxt;
vec<int> pd;
vec<int> e;
int ti = 0;

int dfs(int x, int pr = -1){
    o[x] = pr;
    pd[x] = 1;
    par[x] = 0;
    for(auto i : g[x]){
        if(i == pr) continue;
        vrst[i] = vrst[x] + 1;
        pd[x] += dfs(i, x);
        par[x] += par[i];
    }
    if(g[x].size() == 1){
        par[x]++;
    }
    par[x] = (par[x] - 1) % 2 + 1;
    return pd[x];
}

void dfs2(int x, int pr = -1){
    e[x] = ti; ti++;
    for(int ii = 0; ii < g[x].size(); ii++){
        int i = g[x][ii];
        if(i == pr) continue;
        if(ii == 0){
            nxt[i] = nxt[x];
        }
        else nxt[i] = i;
        dfs2(i, x);
    }
    return;
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q; cin >> n >> q;
    pd.resize(n, 0);
    vrst.resize(n);
    e.resize(n);
    o.resize(n, -1);
    par.resize(n, 0);
    nxt.resize(n);
    g.resize(n);
    For(i, n-1){
        int a, b; cin >> a >> b; a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vrst[0] = 0;
    dfs(0);
    For(i, n){
        int mx = 0;
        int mp = 0;
        For(j, g[i].size()){
            if(g[i][j] == o[i]) continue;
            if(mx < pd[g[i][j]]) {
                mp = j;
            }
        }
        swap(g[i][0], g[i][mp]);
    }
    nxt[0] = 0;
    dfs2(0);
    intervalac seg(n);
    int suc = 0;
    int pl = par[0] % 2;
    For(i, n){
        seg.zmen(e[i], par[i]);
        suc += par[i];
    }
    vec<int> ph(n, 0);
    For(i, n){
        ph[i] = g[i].size();
    }
    For(i, q){
        vec<int> mm;
        pl = par[0];
        int d; cin >> d;
        int zm = 0;
        vec<int> qq;
        For(j, d){
            int a; cin >> a; a--;
            mm.push_back(a);
            ph[a]++;
            if(ph[a] == 2){
                continue;
            }
            qq.push_back(a);
            pl = 1 - pl;
            while(a != -1){
                zm += seg.daj(e[nxt[a]], e[a]);
                a = o[nxt[a]];
            }
        }
        if(pl == 1){
            cout << -1 << endl;
        }
        else cout << suc + zm + d - 2 << endl;
        for(auto i : mm){
            ph[i]--;
        }
        For(j, qq.size()){
            int a = qq[j];
            while(a != -1){
                seg.daj(e[nxt[a]], e[a]);
                a = o[nxt[a]];
            }
        }
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...