oj.uz

Submission #585864

# Submission time Handle Problem Language Result Execution time Memory
585864 2022-06-29T13:06:17 Z MohamedFaresNebili Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 585 ms 15900 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound

        const int MOD = 1000 * 1000 * 1000 + 7;

        int N, Q, R, L, T, timer;
        int s[111111], par[111111];
        int tin[111111], head[111111];
        int st[444444], lazy[444444];
        int vis[111111];
        vector<int> adj[111111];

        void prop(int v, int l, int r) {
            if(l == r || !lazy[v]) return;
            int md = (l + r) / 2;
            int A = md - l + 1, B = r - md;
            st[v * 2] = A - st[v * 2];
            st[v * 2 + 1] = B - st[v * 2 + 1];
            lazy[v * 2] ^= 1, lazy[v * 2 + 1] ^= 1;
            lazy[v] = 0;
        }

        void update(int v, int l, int r, int lo, int hi) {
            prop(v, l, r);
            if(l > hi || r < lo) return;
            if(l >= lo && r <= hi) {
                lazy[v] ^= 1;
                st[v] = r - l + 1 - st[v];
                prop(v, l, r);
                return;
            }
            int md = (l + r) / 2;
            update(v * 2, l, md, lo, hi);
            update(v * 2 + 1, md + 1, r, lo, hi);
            st[v] = st[v * 2] + st[v * 2 + 1];
        }
        void dfs(int v, int p) {
            s[v] = 1; par[v] = p;
            for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u, v); s[v] += s[u];
            }
        }
        void HLD(int v, int p, int t) {
            tin[v] = timer++; head[v] = t;
            int heavy = -1, curr = 0;
            for(auto u : adj[v]) {
                if(u == p) continue;
                if(s[u] > curr) {
                    curr = s[u], heavy = u;
                }
            }
            if(heavy == -1) return;
            HLD(heavy, v, t);
            for(auto u : adj[v]) {
                if(u == p || u == heavy) continue;
                HLD(u, v, u);
            }
        }

		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> Q;
            for(int l = 0; l < N - 1; l++) {
                int U, V; cin >> U >> V;
                adj[U].pb(V), adj[V].pb(U);
            }
            R = 1;
            for(int l = 1; l <= N; l++)
                if(adj[l].size() > 1) R = l;
            dfs(R, 0); HLD(R, 0, R);
            for(int l = 1; l <= N; l++) {
                if(adj[l].size() > 1) continue;
                ++L;
                for(int u = l; u; u = par[head[u]])
                    update(1, 0, N - 1, tin[head[u]], tin[u]);
            }
            while(Q--) {
                T++; int D; cin >> D;
                int A[D]; vector<int> rev;
                int C = D + L;
                for(int l = 0; l < D; l++) {
                    int V; cin >> V; A[l] = V;
                    if(adj[V].size() <= 1 && vis[V] != T) {
                        vis[V] = T, rev.pb(V); --C;
                    }
                }
                if(C & 1) {
                    cout << -1 << "\n";
                    continue;
                }
                for(auto u : rev)
                    for(; u; u = par[head[u]])
                        update(1, 0, N - 1, tin[head[u]], tin[u]);
                for(int l = 0; l < D; l++)
                    for(int u = A[l]; u; u = par[head[u]])
                        update(1, 0, N - 1, tin[head[u]], tin[u]);

                int odd = st[1] + D;
                int even = N - 1 - st[1];
                cout << odd + 2 * even << "\n";

                for(auto u : rev)
                    for(; u; u = par[head[u]])
                        update(1, 0, N - 1, tin[head[u]], tin[u]);
                for(int l = 0; l < D; l++)
                    for(int u = A[l]; u; u = par[head[u]])
                        update(1, 0, N - 1, tin[head[u]], tin[u]);
            }
            return 0;
		}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 264 ms 4688 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3636 KB Output is correct
2 Correct 8 ms 3540 KB Output is correct
3 Correct 76 ms 10356 KB Output is correct
4 Correct 163 ms 9480 KB Output is correct
5 Correct 198 ms 11328 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3668 KB Output is correct
2 Correct 8 ms 3560 KB Output is correct
3 Correct 47 ms 15900 KB Output is correct
4 Correct 112 ms 14916 KB Output is correct
5 Correct 41 ms 14084 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4984 KB Output is correct
2 Correct 89 ms 4664 KB Output is correct
3 Correct 18 ms 4572 KB Output is correct
4 Correct 13 ms 4980 KB Output is correct
5 Correct 18 ms 4940 KB Output is correct
6 Correct 79 ms 5080 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 7696 KB Output is correct
2 Correct 543 ms 7448 KB Output is correct
3 Correct 473 ms 5384 KB Output is correct
4 Correct 535 ms 7500 KB Output is correct
5 Correct 557 ms 7456 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 10800 KB Output is correct
2 Correct 179 ms 12932 KB Output is correct
3 Correct 162 ms 12504 KB Output is correct
4 Correct 161 ms 12856 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 264 ms 4688 KB Output is correct
3 Correct 53 ms 3636 KB Output is correct
4 Correct 8 ms 3540 KB Output is correct
5 Correct 76 ms 10356 KB Output is correct
6 Correct 163 ms 9480 KB Output is correct
7 Correct 198 ms 11328 KB Output is correct
8 Correct 42 ms 3668 KB Output is correct
9 Correct 8 ms 3560 KB Output is correct
10 Correct 47 ms 15900 KB Output is correct
11 Correct 112 ms 14916 KB Output is correct
12 Correct 41 ms 14084 KB Output is correct
13 Correct 126 ms 4984 KB Output is correct
14 Correct 89 ms 4664 KB Output is correct
15 Correct 18 ms 4572 KB Output is correct
16 Correct 13 ms 4980 KB Output is correct
17 Correct 18 ms 4940 KB Output is correct
18 Correct 79 ms 5080 KB Output is correct
19 Correct 312 ms 7696 KB Output is correct
20 Correct 543 ms 7448 KB Output is correct
21 Correct 473 ms 5384 KB Output is correct
22 Correct 535 ms 7500 KB Output is correct
23 Correct 557 ms 7456 KB Output is correct
24 Correct 237 ms 10800 KB Output is correct
25 Correct 179 ms 12932 KB Output is correct
26 Correct 162 ms 12504 KB Output is correct
27 Correct 161 ms 12856 KB Output is correct
28 Correct 393 ms 7232 KB Output is correct
29 Correct 231 ms 12240 KB Output is correct
30 Correct 74 ms 11120 KB Output is correct
31 Correct 109 ms 14976 KB Output is correct
32 Correct 585 ms 7452 KB Output is correct
33 Correct 240 ms 11756 KB Output is correct
34 Correct 268 ms 11936 KB Output is correct
35 Correct 285 ms 12772 KB Output is correct