Submission #976245

#	Time	Username	Problem	Language	Result	Execution time	Memory
976245		efedmrlr	Spring cleaning (CEOI20_cleaning)	C++17	26 / 100	98 ms	36672 KiB

cleaning

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,popcnt")
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define MP make_pair

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;
const int LGN = 20;
int n, q;
vector<vector<int> > adj(N, vector<int>());
array<vector<int>, LGN> anc;
array<vector<int>, LGN> diff; 
vector<int> dep(N, 0);
vector<int> tin(N, 0);
//virt stuff
vector<bool> mark(N, 0);
vector<int> vals(N, 0);
vector<vector<int> > virt(N, vector<int>());
vector<int> p(N, 0);

int tim = 0;
int ans = 0;
int leaf = 0;
int dfs(int node, int par) {
    anc[0][node] = par;
    tin[node] = tim++;
    if(adj[node].size() == 1 && par) {
        leaf++;
        ans++;
        diff[0][node] = 1;
        return 1;
    }
    int ret = 0;
    if(par == 0 && adj[node].size() == 1) leaf++;
    for(auto c : adj[node]) {
        if(c == par) continue;
        dep[c] = dep[node] + 1;
        ret += dfs(c, node);
    }
    // cout << "node: " << node << " ret:" << ret << "\n";
    if(par == 0) {
        return 0;
    }
    if(ret & 1) {  
        ans++;
        diff[0][node] = 1;
        return 1;
    }
    else {
        ans += 2;
        diff[0][node] = -1;
        return 2;
    }
}

void calc() {
    for(int k = 1; k < LGN; k++) {
        for(int i = 1; i <= n; i++) {
            anc[k][i] = anc[k - 1][anc[k - 1][i]];
            diff[k][i] = diff[k - 1][i] + (diff[k - 1][anc[k - 1][i]]);
        }
    } 
}

int kth_anc(int x, int k) {
    for(int i = 0; i < LGN; i++) {
        if(k & (1 << i)) x = anc[i][x];
    }
    return x;
}
int k_sum(int x, int k) {
    int ret = 0;
    for(int i = 0; i < LGN; i++) {
        if(k & (1 << i)) {
            ret += diff[i][x];
            x = anc[i][x];
        } 
    }
    return ret;
}
int lca(int x, int y) {
    if(dep[x] > dep[y]) swap(x, y);
    y = kth_anc(y, dep[y] - dep[x]);
    if(x == y) return x;
    for(int i = LGN - 1; i >= 0; i--) {
        if(anc[i][x] != anc[i][y]) {
            x = anc[i][x];
            y = anc[i][y];
        }
    }
    return anc[0][x];
}
int res = 0;
bool dfs2(int node, int par) {
    bool cur = mark[node];
    for(auto c : virt[node]) {
        assert(c != par);
        cur ^= dfs2(c, node);
    }
    if(cur) {
        res += vals[node];
    }
    return cur;
}


void solve() {
    cin >> n >> q;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    REP(i, LGN) {
        anc[i].assign(n + 3, 0);
        diff[i].assign(n + 3, 0);
    }
    dfs(1, 0);
    anc[0][1] = 1;
    calc();
    auto comp = [](int x, int y) {
        return tin[x] < tin[y];
    };
    // cout << "ans:" << ans << "\n";
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dif:" << diff[0][i] << "\n";
    // }

    REP(z, q) {
        // cout << "query:" << z << endl;
        int d;
        cin >> d;
        res = ans + d;
        int lv = leaf + d;
        vector<int> a(d);
        REP(i, d) {
            cin >> a[i];
            
        }
        sort(all(a));
        vector<array<int, 2> > tmp;
        for(int i = 0; i < d; i++) {
            if(tmp.size() && tmp.back()[0] == a[i]) tmp[tmp.size() - 1][1]++;
            else {
                tmp.pb({a[i], 1});
            }
        }
        a.clear();
        for(auto &c : tmp) {
            if(adj[c[0]].size() == 1) {
                lv--;
            }
        }
        if(lv & 1) {
            cout << "-1\n";
            continue;
        }

        // cout << "new a: ";
        for(auto &c : tmp) {
            if((c[1] & 1) && (adj[c[0]].size() > 1)) {
                a.pb(c[0]);
                // cout << c[0] << " ";
            }
            else if(!(c[1] & 1)) {
                a.pb(c[0]);
            }
        }
        // cout << endl;
        

        if(a.empty()) {
            cout << res << "\n";
            continue;
        }
        for(auto c : a) {
            mark[c] = 1;
        }
        sort(all(a), comp);
        // cout << "aaa" << endl;
        d = (int)a.size();
        for(int i = 0; i < d - 1; i++) {
            a.pb(lca(a[i], a[i + 1]));
        }
        
        sort(all(a), comp);
        a.resize(unique(all(a)) - a.begin());
        d = (int) a.size();
        vector<int> st;
        st.pb(a[0]);
        for(int i = 1; i < d; i++) {
            assert(st.size());
            while(lca(st.back(), a[i]) != st.back()) {
                st.pop_back();
                assert(st.size());
            }
            virt[st.back()].pb(a[i]);
            p[a[i]] = st.back();
            st.pb(a[i]);
        }
        vals[a[0]] = k_sum(a[0], dep[a[0]] - dep[1] + 1);
        for(int i = 1; i < d; i++) {
            vals[a[i]] = k_sum(a[i], dep[a[i]] - dep[p[a[i]]]); 
        }
        // for(int i = 0; i < d; i++) {
        //     cout << "ai:" << a[i] << " val:" << vals[a[i]] << " mark:" << mark[a[i]] << "\n";
        // }
        // cout << "res before:" << res << "\n";
        dfs2(a[0], 0);
        cout << res << "\n";
        for(auto c : a) {
            mark[c] = 0;
            vals[c] = 0;
            p[c] = 0;
            virt[c].clear();
        }

    }
}

signed main() {
    fastio();
    solve();
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 17 / 17
• Subtask 7: 0 / 30