oj.uz

Submission #578205

# Submission time Handle Problem Language Result Execution time Memory
578205 2022-06-16T08:10:12 Z talant117408 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 282 ms 23840 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 2e5+7;
vector <vector <int>> graph(N);
int root, subtree[N], depth[N], parent[N], added[N];
int turn[N];
int head[N], heavy[N], pos[N], t;
ll ans;
ll tree[N*4];
bool lz[N*4];

struct query {
    int saizu;
    vector <int> cling;
    query() {
        saizu = 0;
    }
    query(int n) {
        saizu = n;
        cling.resize(n);
    }
};

void push(int v, int l, int r) {
    if (lz[v]) {
        tree[v] *= -1;
        if (l != r) {
            lz[v*2] ^= 1;
            lz[v*2+1] ^= 1;
        }
        lz[v] = 0;
    }
}

void build(int v, int l, int r) {
    if (l == r) {
        tree[v] = turn[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(v*2, l, mid);
    build(v*2+1, mid+1, r);
    tree[v] = tree[v*2]+tree[v*2+1];
}

void update(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[v] ^= 1;
        push(v, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(v*2, l, mid, ql, qr);
    update(v*2+1, mid+1, r, ql, qr);
    tree[v] = tree[v*2]+tree[v*2+1];
}

ll get(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return 0;
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l+r) >> 1;
    return get(v*2, l, mid, ql, qr)+get(v*2+1, mid+1, r, ql, qr);
}

ll get(int n, int x) {
    ll res = 0;
    while (head[n] != root) {
        res += get(1, 1, x, pos[head[n]], pos[n]);
        update(1, 1, x, pos[head[n]], pos[n]);
        n = parent[head[n]];
    }
    res += get(1, 1, x, pos[root], pos[n]);
    update(1, 1, x, pos[root], pos[n]);
    return res;
}

void clear(int n, int x) {
    while (head[n] != root) {
        update(1, 1, x, pos[head[n]], pos[n]);
        n = parent[head[n]];
    }
    update(1, 1, x, pos[root], pos[n]);
}

int dfs(int v, int p) {
    subtree[v] = (sz(graph[v]) == 1 ? 1 : 0);
    parent[v] = p;
    int saizu = 1;
    int mx_saizu = 0;
    for (auto to : graph[v]) {
        if (to == p) {
            continue;
        }
        depth[to] = depth[v] + 1;
        auto tmp = dfs(to, v);
        saizu += tmp;
        if (tmp > mx_saizu) {
            mx_saizu = tmp;
            heavy[v] = to;
        }
        subtree[v] += subtree[to];
    }
    if (v != root)
        ans += 2 - (subtree[v] % 2);
    return saizu;
}

void decompose(int v, int h) {
    head[v] = h; pos[v] = ++t;
    if (heavy[v] != -1) decompose(heavy[v], h);
    for (auto to : graph[v]) {
        if (to != parent[v] && to != heavy[v]) {
            decompose(to, to);
        }
    }
}

void initiate(int n) {
    for (int i = 1; i <= n; i++) {
        heavy[i] = -1;
        if (sz(graph[i]) > 1) {
            root = i;
        }
    }
    dfs(root, root);
    decompose(root, root);
    for (int i = 1; i <= n; i++) {
        turn[pos[i]] = (subtree[i]&1 ? 1 : -1);
    }
    turn[pos[root]] = 0;
    build(1, 1, n);
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector <query> queries;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    for (int i = 0; i < q; i++) {
        int k;
        cin >> k;
        queries.pb(query(k));
        for (int j = 0; j < k; j++) {
            cin >> queries[i].cling[j];
        }
    }
    initiate(n);
    for (int test = 0; test < q; test++) {
        ll tmp = queries[test].saizu;
        int l = 0;
        auto leaves = queries[test].cling;
        
        for (auto p : leaves) {
            if (sz(graph[p]) == 1) {
                added[p]++;
                if (added[p] == 1) {
                    continue;
                }
            }
            l++;
            tmp += get(p, n);
        }
        
        if ((subtree[root]+l)&1) cout << -1 << endl;
        else cout << ans+tmp << endl;
        
        for (auto p : leaves) {
            if (sz(graph[p]) == 1) {
                added[p]--;
                if (added[p] == 0) {
                    continue;
                }
            }
            clear(p, n);
        }
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
7 5
1 2
1 3
2 4
2 5
3 6
3 7
1 1
2 1 1
2 7 7
2 6 7
2 4 7
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 143 ms 7564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5984 KB Output is correct
2 Correct 69 ms 5980 KB Output is correct
3 Correct 31 ms 13992 KB Output is correct
4 Correct 96 ms 12676 KB Output is correct
5 Correct 94 ms 14660 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6612 KB Output is correct
2 Correct 54 ms 6612 KB Output is correct
3 Correct 61 ms 22412 KB Output is correct
4 Correct 141 ms 21760 KB Output is correct
5 Correct 44 ms 21012 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 7908 KB Output is correct
2 Correct 46 ms 7068 KB Output is correct
3 Correct 11 ms 6868 KB Output is correct
4 Correct 11 ms 7380 KB Output is correct
5 Correct 14 ms 7508 KB Output is correct
6 Correct 60 ms 7764 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 14668 KB Output is correct
2 Correct 281 ms 10944 KB Output is correct
3 Correct 206 ms 8304 KB Output is correct
4 Correct 245 ms 10952 KB Output is correct
5 Correct 251 ms 11096 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 20580 KB Output is correct
2 Correct 121 ms 23840 KB Output is correct
3 Correct 182 ms 23096 KB Output is correct
4 Correct 167 ms 23672 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 143 ms 7564 KB Output is correct
3 Correct 67 ms 5984 KB Output is correct
4 Correct 69 ms 5980 KB Output is correct
5 Correct 31 ms 13992 KB Output is correct
6 Correct 96 ms 12676 KB Output is correct
7 Correct 94 ms 14660 KB Output is correct
8 Correct 52 ms 6612 KB Output is correct
9 Correct 54 ms 6612 KB Output is correct
10 Correct 61 ms 22412 KB Output is correct
11 Correct 141 ms 21760 KB Output is correct
12 Correct 44 ms 21012 KB Output is correct
13 Correct 98 ms 7908 KB Output is correct
14 Correct 46 ms 7068 KB Output is correct
15 Correct 11 ms 6868 KB Output is correct
16 Correct 11 ms 7380 KB Output is correct
17 Correct 14 ms 7508 KB Output is correct
18 Correct 60 ms 7764 KB Output is correct
19 Correct 176 ms 14668 KB Output is correct
20 Correct 281 ms 10944 KB Output is correct
21 Correct 206 ms 8304 KB Output is correct
22 Correct 245 ms 10952 KB Output is correct
23 Correct 251 ms 11096 KB Output is correct
24 Correct 282 ms 20580 KB Output is correct
25 Correct 121 ms 23840 KB Output is correct
26 Correct 182 ms 23096 KB Output is correct
27 Correct 167 ms 23672 KB Output is correct
28 Correct 176 ms 10704 KB Output is correct
29 Correct 173 ms 17028 KB Output is correct
30 Correct 89 ms 14672 KB Output is correct
31 Correct 119 ms 21764 KB Output is correct
32 Correct 238 ms 10964 KB Output is correct
33 Correct 150 ms 16720 KB Output is correct
34 Correct 187 ms 16832 KB Output is correct
35 Correct 179 ms 17868 KB Output is correct