Submission #540149

#	Time	Username	Problem	Language	Result	Execution time	Memory
540149		yuto1115	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	466 ms	21916 KiB

cleaning

#include <bits/stdc++.h>
#include <cassert>
#include <vector>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template <class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> void vecout(const vector<T> &v, char div = '\n') {
    int n = SZ(v);
    rep(i, n) cout << v[i] << (i == n - 1 ? '\n' : div);
}

using S = P;
const S e = {0, 0};
using F = int;
const F id = 0;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
S mapping(F f, S x) { return (f ? P(x.second, x.first) : x); }
F compose(F g, F f) { return g ^ f; }

class lazy_segtree {
    vector<S> d;
    vector<F> lz;
    int n, log;
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < n) lz[k] = compose(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id;
    }

  public:
    lazy_segtree(int _n, const vector<S> &init) {
        log = 0;
        while (1 << log < _n) ++log;
        n = 1 << log;
        d.assign(2 * n, e);
        lz.assign(n, id);
        rep(i, _n) d[n + i] = init[i];
        rrep(i, n) update(i);
    }
    vector<S> all_get() {
        rep(i, n) push(i);
        return vector<S>(d.begin() + n, d.end());
    }
    S get(int p) {
        assert(0 <= p and p < n);
        p += n;
        for (int i = log; i >= 1; --i) {
            push(p >> i);
        }
        return d[p];
    }
    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; --i) {
            if (l >> i << i != l) push(l >> i);
            if (r >> i << i != r) push(r >> i);
        }
        S res = e;
        while (l < r) {
            if (l & 1) res = op(res, d[l++]);
            if (r & 1) res = op(res, d[--r]);
            l /= 2, r /= 2;
        }
        return res;
    }
    void apply(int l, int r, F f) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; --i) {
            if (l >> i << i != l) push(l >> i);
            if (r >> i << i != r) push(r >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l /= 2, r /= 2;
            }
            l = l2, r = r2;
        }
        for (int i = 1; i <= log; ++i) {
            if (l >> i << i != l) update(l >> i);
            if (r >> i << i != r) update(r >> i);
        }
    }
};

class HLD {
    int n;
    vvi G;
    int root;
    vi ord, par, head, rev, sz;

    void dfs_sz(int u, int p) {
        par[u] = p;
        sz[u] = 1;
        if (G[u][0] == p) swap(G[u][0], G[u].back());
        for (int &v : G[u]) {
            if (v == p) continue;
            dfs_sz(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[G[u][0]]) swap(G[u][0], v);
        }
    }

    void dfs_hld(int u, int p, int &k) {
        ord[u] = k++;
        rev[ord[u]] = u;
        for (int &v : G[u]) {
            if (v == p) continue;
            head[v] = (v == G[u][0] ? head[u] : v);
            dfs_hld(v, u, k);
        }
    }

  public:
    HLD(const vvi &_G, int r) : G(_G), root(r) {
        n = SZ(G);
        ord.resize(n);
        par.resize(n);
        head.resize(n);
        rev.resize(n);
        sz.resize(n);
        dfs_sz(root, -1);
        head[root] = root;
        int k = 0;
        dfs_hld(root, -1, k);
    }

    template <class Q> void apply(int u, int v, const Q &f) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        for (;; v = par[head[v]]) {
            if (ord[u] > ord[v]) swap(u, v);
            if (head[u] == head[v]) break;
            f(ord[head[v]], ord[v] + 1);
        }
        f(ord[u], ord[v] + 1);
    }

    template <class T, class Q, class M>
    T get(int u, int v, T e, const Q &f, const M &mg) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        T res = e;
        for (;; v = par[head[v]]) {
            if (ord[u] > ord[v]) swap(u, v);
            if (head[u] == head[v]) break;
            res = mg(res, f(ord[head[v]], ord[v] + 1));
        }
        res = mg(res, f(ord[u], ord[v] + 1));
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vvi G(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    int root = (SZ(G[0]) == 1 ? 1 : 0);
    HLD hld(G, root);
    lazy_segtree st(n, vp(n, {1, 0}));
    auto flip = [&](int l, int r) { st.apply(l, r, 1); };
    auto count = [&](int l, int r) { return st.prod(l, r); };
    rep(i, n) {
        if (SZ(G[i]) == 1) hld.apply(i, root, flip);
    }
    vp init = st.all_get();
    int sc = 0;
    for (auto p : init) {
        if (p.first) sc += 2;
        if (p.second) sc += 1;
    }
    while (q--) {
        int d;
        cin >> d;
        vi a(d);
        for (int &i : a) cin >> i, --i;
        unordered_set<int> seen;
        int ans = sc;
        vi hist;
        for (int i : a) {
            if (SZ(G[i]) == 1 and !seen.count(i)) {
                seen.insert(i);
            } else {
                P p = hld.get(i, root, e, count, op);
                ans -= p.first;
                ans += p.second;
                hld.apply(i, root, flip);
                hist.pb(i);
            }
            ++ans;
        }
        if (st.get(0).second)
            ans = -1;
        else
            ans -= 2;
        cout << ans << '\n';
        for (int i : hist) {
            hld.apply(i, root, flip);
        }
    }
}

• 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