제출 #585861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585861		MohamedFaresNebili	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	601 ms	16940 KiB

cleaning

#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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30