oj.uz

Submission #540149

# Submission time Handle Problem Language Result Execution time Memory
540149 2022-03-19T11:57:26 Z yuto1115 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 466 ms 21916 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 171 ms 4624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2204 KB Output is correct
2 Correct 81 ms 2284 KB Output is correct
3 Correct 98 ms 18596 KB Output is correct
4 Correct 148 ms 17480 KB Output is correct
5 Correct 188 ms 21856 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2796 KB Output is correct
2 Correct 54 ms 2680 KB Output is correct
3 Correct 56 ms 21824 KB Output is correct
4 Correct 120 ms 21916 KB Output is correct
5 Correct 49 ms 20100 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 4924 KB Output is correct
2 Correct 71 ms 4236 KB Output is correct
3 Correct 24 ms 4012 KB Output is correct
4 Correct 16 ms 4236 KB Output is correct
5 Correct 18 ms 4404 KB Output is correct
6 Correct 70 ms 4588 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 12132 KB Output is correct
2 Correct 396 ms 12072 KB Output is correct
3 Correct 303 ms 6700 KB Output is correct
4 Correct 409 ms 12000 KB Output is correct
5 Correct 434 ms 12104 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 19504 KB Output is correct
2 Correct 206 ms 20624 KB Output is correct
3 Correct 246 ms 20668 KB Output is correct
4 Correct 249 ms 20380 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 171 ms 4624 KB Output is correct
3 Correct 73 ms 2204 KB Output is correct
4 Correct 81 ms 2284 KB Output is correct
5 Correct 98 ms 18596 KB Output is correct
6 Correct 148 ms 17480 KB Output is correct
7 Correct 188 ms 21856 KB Output is correct
8 Correct 56 ms 2796 KB Output is correct
9 Correct 54 ms 2680 KB Output is correct
10 Correct 56 ms 21824 KB Output is correct
11 Correct 120 ms 21916 KB Output is correct
12 Correct 49 ms 20100 KB Output is correct
13 Correct 107 ms 4924 KB Output is correct
14 Correct 71 ms 4236 KB Output is correct
15 Correct 24 ms 4012 KB Output is correct
16 Correct 16 ms 4236 KB Output is correct
17 Correct 18 ms 4404 KB Output is correct
18 Correct 70 ms 4588 KB Output is correct
19 Correct 326 ms 12132 KB Output is correct
20 Correct 396 ms 12072 KB Output is correct
21 Correct 303 ms 6700 KB Output is correct
22 Correct 409 ms 12000 KB Output is correct
23 Correct 434 ms 12104 KB Output is correct
24 Correct 408 ms 19504 KB Output is correct
25 Correct 206 ms 20624 KB Output is correct
26 Correct 246 ms 20668 KB Output is correct
27 Correct 249 ms 20380 KB Output is correct
28 Correct 267 ms 11384 KB Output is correct
29 Correct 203 ms 20184 KB Output is correct
30 Correct 176 ms 21832 KB Output is correct
31 Correct 145 ms 21908 KB Output is correct
32 Correct 466 ms 12068 KB Output is correct
33 Correct 198 ms 17092 KB Output is correct
34 Correct 202 ms 20292 KB Output is correct
35 Correct 235 ms 20176 KB Output is correct