oj.uz

Submission #895301

# Submission time Handle Problem Language Result Execution time Memory
895301 2023-12-29T18:15:45 Z themm1 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 300 ms 24284 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

struct LazySegtree {
        int N;
        vector<int> sums, flipped;
        LazySegtree(vector<int> &a) {
                N = pow(2, ceil(log2(sz(a))));
                sums.assign(2 * N, 0);
                flipped.assign(2 * N, 0);
                for (int i = 0; i < sz(a); i++) sums[i + N] = a[i];
                for (int i = N - 1; i >= 1; i--) sums[i] = sums[i * 2] + sums[i * 2 + 1];
                // dmp(sums);
                // dmp(flipped);
        }

        int get_sum(int idx, int i, int j) {
                if (flipped[idx]) return (j - i) - sums[idx];
                return sums[idx];
        }

        void push_lazy(int idx, int i, int j) {
                if (flipped[idx]) {
                        flipped[idx * 2] ^= 1;
                        flipped[idx * 2 + 1] ^= 1;
                        flipped[idx] = 0;
                }
        }

        int query(int l, int r, int i, int j, int idx = 1) {
                // aktualny je cely v povodnom
                if (l <= i && j <= r) {
                        return get_sum(idx, i, j);
                // prekryva sa
                } else if ((i <= l && l < j) || (i < r && r <= j)) {
                        push_lazy(idx, i, j);
                        int mid = (i + j) / 2;
                        return query(l, r, i, mid, idx * 2) + query(l, r, mid, j, idx * 2 + 1);
                }
                return 0;
        }

        void lazy_update(int l, int r, int i, int j, int idx = 1) {
                if (l <= i && j <= r) {
                        flipped[idx] ^= 1;
                } else if ((i <= l && l < j) || (i < r && r <= j)) {
                        push_lazy(idx, i, j);
                        int mid = (i + j) / 2;
                        lazy_update(l, r, i, mid, idx * 2);
                        lazy_update(l, r, mid, j, idx * 2 + 1);
                        sums[idx] = get_sum(idx * 2, i, mid) + get_sum(idx * 2 + 1, mid, j);
                }
        }

        void print_row(int l, int r) {
                for (int i = l; i < r; i++) cout << query(i, i + 1, 0, N) << " ";
                cout << endl;
        }
};

int N, Q;
vector<vector<int>> g;
vector<int> intimes, tops, is_evens, parents;

int dfs1(int v, int p) {
        int size = 1, mx = 0, mxi = -1;
        is_evens[v] = (sz(g[v]) == 1) ? 0 : 1;
        parents[v] = p;
        for (int i = 0; i < sz(g[v]); i++) if (g[v][i] != p) {
                int u = g[v][i];
                int usz = dfs1(u, v);
                if (usz > mx) {
                        mx = usz;
                        mxi = i;
                }
                size += usz;
                if (!is_evens[u]) is_evens[v] ^= 1;
        }
        if (mxi != -1) swap(g[v][0], g[v][mxi]);
        return size;
}

int dfs2(int v, int p, int time, int top) {
        intimes[v] = time;
        tops[v] = top;
        for (int i = 0; i < sz(g[v]); i++) if (g[v][i] != p) {
                int u = g[v][i];
                if (i == 0) time = dfs2(u, v, time + 1, top);
                else time = dfs2(u, v, time + 1, u);
        }
        return time;
}

void solve() {
        cin >> N >> Q;
        g.assign(N, {});
        is_evens.assign(N, 0);
        parents.assign(N, -1);
        intimes.assign(N, 0);
        tops.assign(N, 0);
        for (int i = 0; i < N - 1; i++) {
                int u, v;
                cin >> u >> v;
                u--;
                v--;
                g[u].pb(v);
                g[v].pb(u);
        }
        int root = 0, leaves = 0;
        for (int i = 0; i < N; i++) if (sz(g[i]) == 1) leaves++;
        dfs1(root, -1);
        dfs2(root, -1, 0, root);

        vector<int> base(N, 0);
        for (int i = 0; i < N; i++) base[intimes[i]] = is_evens[i];
        LazySegtree st(base);
        // st.print_row(0, N);
        while (Q--) {
                int K;
                cin >> K;
                bool even = ((leaves + K) % 2 == 0);
                map<int, int> m;
                for (int i = 0; i < K; i++) {
                        int v;
                        cin >> v;
                        v--;
                        m[v]++;
                }
                map<pii, int> updates;
                int x = 0;
                for (pii kv : m) {
                        int v = kv.ff;
                        if (sz(g[v]) == 1) even ^= 1;
                        if ((sz(g[v]) == 1 && kv.ss % 2 == 1) || (sz(g[v]) != 1 && kv.ss % 2 == 0)) continue;
                        while (v != -1) {
                                pii pr = { intimes[tops[v]], intimes[v] + 1 };
                                updates[pr]++;
                                v = parents[tops[v]];
                                x++;
                        }
                }
                for (auto kv : updates) if (kv.ss % 2 == 1) st.lazy_update(kv.ff.ff, kv.ff.ss, 0, st.N);
                if (!even) cout << -1 << endl;
                else {
                        int even_cnt = st.query(0, N, 0, st.N);
                        int ans = N + K - 2 + even_cnt;
                        cout << ans << endl;
                }
                for (auto kv : updates) if (kv.ss % 2 == 1) st.lazy_update(kv.ff.ff, kv.ff.ss, 0, st.N);
        }
}

int32_t main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        // clock_t start = clock();
        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
        // cout << (clock() - start) / 1000 << " ms" << endl;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 88 ms 3572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1372 KB Output is correct
2 Correct 11 ms 1368 KB Output is correct
3 Correct 21 ms 10960 KB Output is correct
4 Correct 50 ms 12104 KB Output is correct
5 Correct 67 ms 15184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2140 KB Output is correct
2 Correct 14 ms 2080 KB Output is correct
3 Correct 51 ms 20052 KB Output is correct
4 Correct 78 ms 24284 KB Output is correct
5 Correct 30 ms 18480 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3920 KB Output is correct
2 Correct 31 ms 3164 KB Output is correct
3 Correct 7 ms 2648 KB Output is correct
4 Correct 8 ms 3164 KB Output is correct
5 Correct 9 ms 3420 KB Output is correct
6 Correct 50 ms 3764 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 7524 KB Output is correct
2 Correct 164 ms 7880 KB Output is correct
3 Correct 156 ms 4436 KB Output is correct
4 Correct 172 ms 7836 KB Output is correct
5 Correct 162 ms 7672 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 11780 KB Output is correct
2 Correct 203 ms 15416 KB Output is correct
3 Correct 249 ms 14932 KB Output is correct
4 Correct 223 ms 16448 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 88 ms 3572 KB Output is correct
3 Correct 11 ms 1372 KB Output is correct
4 Correct 11 ms 1368 KB Output is correct
5 Correct 21 ms 10960 KB Output is correct
6 Correct 50 ms 12104 KB Output is correct
7 Correct 67 ms 15184 KB Output is correct
8 Correct 14 ms 2140 KB Output is correct
9 Correct 14 ms 2080 KB Output is correct
10 Correct 51 ms 20052 KB Output is correct
11 Correct 78 ms 24284 KB Output is correct
12 Correct 30 ms 18480 KB Output is correct
13 Correct 47 ms 3920 KB Output is correct
14 Correct 31 ms 3164 KB Output is correct
15 Correct 7 ms 2648 KB Output is correct
16 Correct 8 ms 3164 KB Output is correct
17 Correct 9 ms 3420 KB Output is correct
18 Correct 50 ms 3764 KB Output is correct
19 Correct 230 ms 7524 KB Output is correct
20 Correct 164 ms 7880 KB Output is correct
21 Correct 156 ms 4436 KB Output is correct
22 Correct 172 ms 7836 KB Output is correct
23 Correct 162 ms 7672 KB Output is correct
24 Correct 300 ms 11780 KB Output is correct
25 Correct 203 ms 15416 KB Output is correct
26 Correct 249 ms 14932 KB Output is correct
27 Correct 223 ms 16448 KB Output is correct
28 Correct 116 ms 7508 KB Output is correct
29 Correct 80 ms 14708 KB Output is correct
30 Correct 57 ms 15304 KB Output is correct
31 Correct 83 ms 24144 KB Output is correct
32 Correct 160 ms 8144 KB Output is correct
33 Correct 125 ms 13392 KB Output is correct
34 Correct 150 ms 15908 KB Output is correct
35 Correct 137 ms 15844 KB Output is correct