oj.uz

Submission #585861

# Submission time Handle Problem Language Result Execution time Memory
585861 2022-06-29T13:05:09 Z MohamedFaresNebili Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 601 ms 16940 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, 1, N, 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, 1, N, tin[head[u]], tin[u]);
                for(int l = 0; l < D; l++)
                    for(int u = A[l]; u; u = par[head[u]])
                        update(1, 1, N, 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, 1, N, tin[head[u]], tin[u]);
                for(int l = 0; l < D; l++)
                    for(int u = A[l]; u; u = par[head[u]])
                        update(1, 1, N, 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 262 ms 5292 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3912 KB Output is correct
2 Correct 8 ms 3900 KB Output is correct
3 Correct 56 ms 11000 KB Output is correct
4 Correct 109 ms 10544 KB Output is correct
5 Correct 148 ms 12456 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4052 KB Output is correct
2 Correct 13 ms 3916 KB Output is correct
3 Correct 46 ms 16940 KB Output is correct
4 Correct 98 ms 16376 KB Output is correct
5 Correct 37 ms 14924 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5624 KB Output is correct
2 Correct 126 ms 4904 KB Output is correct
3 Correct 18 ms 4616 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 17 ms 5044 KB Output is correct
6 Correct 77 ms 5444 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 8816 KB Output is correct
2 Correct 536 ms 8664 KB Output is correct
3 Correct 425 ms 6004 KB Output is correct
4 Correct 565 ms 8692 KB Output is correct
5 Correct 564 ms 8584 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 12604 KB Output is correct
2 Correct 185 ms 14704 KB Output is correct
3 Correct 150 ms 14244 KB Output is correct
4 Correct 171 ms 14676 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 262 ms 5292 KB Output is correct
3 Correct 32 ms 3912 KB Output is correct
4 Correct 8 ms 3900 KB Output is correct
5 Correct 56 ms 11000 KB Output is correct
6 Correct 109 ms 10544 KB Output is correct
7 Correct 148 ms 12456 KB Output is correct
8 Correct 42 ms 4052 KB Output is correct
9 Correct 13 ms 3916 KB Output is correct
10 Correct 46 ms 16940 KB Output is correct
11 Correct 98 ms 16376 KB Output is correct
12 Correct 37 ms 14924 KB Output is correct
13 Correct 115 ms 5624 KB Output is correct
14 Correct 126 ms 4904 KB Output is correct
15 Correct 18 ms 4616 KB Output is correct
16 Correct 13 ms 4940 KB Output is correct
17 Correct 17 ms 5044 KB Output is correct
18 Correct 77 ms 5444 KB Output is correct
19 Correct 267 ms 8816 KB Output is correct
20 Correct 536 ms 8664 KB Output is correct
21 Correct 425 ms 6004 KB Output is correct
22 Correct 565 ms 8692 KB Output is correct
23 Correct 564 ms 8584 KB Output is correct
24 Correct 249 ms 12604 KB Output is correct
25 Correct 185 ms 14704 KB Output is correct
26 Correct 150 ms 14244 KB Output is correct
27 Correct 171 ms 14676 KB Output is correct
28 Correct 361 ms 8396 KB Output is correct
29 Correct 211 ms 13708 KB Output is correct
30 Correct 54 ms 12356 KB Output is correct
31 Correct 109 ms 16400 KB Output is correct
32 Correct 601 ms 8664 KB Output is correct
33 Correct 239 ms 13004 KB Output is correct
34 Correct 236 ms 13564 KB Output is correct
35 Correct 261 ms 14252 KB Output is correct