oj.uz

Submission #585876

# Submission time Handle Problem Language Result Execution time Memory
585876 2022-06-29T13:19:28 Z MohamedFaresNebili Spring cleaning (CEOI20_cleaning) C++14
28 / 100
 634 ms 18948 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[100001], par[100001];
        int tin[100001], head[100001], heavy[100001];
        int st[400004], lazy[400004];
        int vis[100001];
        vector<int> adj[100001];

        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; heavy[v] = 0;
            if(p != 0) adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
            for(auto u : adj[v]) {
                dfs(u, v); s[v] += s[u];
                if(s[u] > s[heavy[v]])
                    heavy[v] = u;
            }
        }
        void HLD(int v, int p, int t) {
            tin[v] = timer++; head[v] = t;
            if(heavy[v] == 0) return;
            HLD(heavy[v], v, t);
            for(auto u : adj[v]) {
                if(u == heavy[v]) 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; break;
                }
            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 << endl;
                    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 << endl;

                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 1 ms 2644 KB Output is correct
2 Incorrect 157 ms 5136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3540 KB Output is correct
2 Correct 13 ms 3540 KB Output is correct
3 Correct 96 ms 11136 KB Output is correct
4 Correct 160 ms 10460 KB Output is correct
5 Correct 209 ms 12348 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3864 KB Output is correct
2 Correct 10 ms 3924 KB Output is correct
3 Incorrect 65 ms 18948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 5672 KB Output is correct
2 Incorrect 85 ms 4716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 8784 KB Output is correct
2 Correct 562 ms 8588 KB Output is correct
3 Correct 465 ms 6024 KB Output is correct
4 Correct 634 ms 8592 KB Output is correct
5 Correct 585 ms 8524 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 603 ms 12228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 157 ms 5136 KB Output isn't correct
3 Halted 0 ms 0 KB -