oj.uz

Submission #964494

# Submission time Handle Problem Language Result Execution time Memory
964494 2024-04-17T02:16:24 Z Ghetto Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 258 ms 71008 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pib = pair<int, bool>;
const int MAX_N = 1e5 + 5, MAX_Q = 1e5 + 5;;
 
int n, q;
vector<int> adj[MAX_N];
vector<int> upd[MAX_Q];
 
int root;
vector<int> child[MAX_N];
bool is_1[MAX_N];
void dfs1(int u, int par) {
    is_1[u] = (bool) (adj[u].size() == 1);
    for (int v : adj[u]) {
        if (v == par) continue;
        child[u].push_back(v);
        dfs1(v, u);
        if (is_1[v]) is_1[u] = !is_1[u];
    }
}
int n_1s[MAX_N], n_0s[MAX_N]; // From root to u
void dfs2(int u) {
    n_1s[u] += is_1[u], n_0s[u] += !is_1[u];
    for (int v : child[u]) {
        n_1s[v] += n_1s[u], n_0s[v] += n_0s[u];
        dfs2(v);
    }
}
int tot_n_1s, tot_n_0s;
void precomp1() {
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1) continue;
        root = i;
        dfs1(root, -1);
        break;
    }
    dfs2(root);
    for (int i = 1; i <= n; i++) 
        tot_n_1s += is_1[i], tot_n_0s += !is_1[i];     
}
 
int new_child_size[MAX_N];
int n_leaves[MAX_Q];
int extra_n_1s[MAX_Q];
unordered_set<int> queries_w_flip1[MAX_N];
void precomp2(int query) {
    for (int u : upd[query]) {
        extra_n_1s[query]++;
        if (new_child_size[u]) {
            n_leaves[query]++;
            if (queries_w_flip1[u].count(query)) queries_w_flip1[u].erase(query);
            else queries_w_flip1[u].insert(query);
        }
        new_child_size[u]++;
    }
    for (int u : upd[query]) new_child_size[u]--;
}
void init() {
    for (int i = 1; i <= n; i++) new_child_size[i] = child[i].size();
    int tot_n_leaves = 0;
    for (int i = 1; i <= n; i++) tot_n_leaves += (bool) child[i].empty();
    for (int i = 1; i <= q; i++) n_leaves[i] = tot_n_leaves;
}
 
unordered_map<int, int> queries_w_flip2[MAX_N]; // {query, prev flipped}
vector<pii> flip_path[MAX_Q]; // {high, low (not incl.)}
void dfs3(int u) {
    unordered_map<int, bool> spec_queries; // {query, flip state}
    for (int query : queries_w_flip1[u]) queries_w_flip2[u].insert({query, u});
 
    for (int v : child[u]) {
        dfs3(v);
 
        if (queries_w_flip2[u].size() < queries_w_flip2[v].size()) queries_w_flip2[u].swap(queries_w_flip2[v]);
        for (pii el : queries_w_flip2[v]) {
            if (spec_queries.count(el.first)) {
                flip_path[el.first].push_back({el.second, u});
                spec_queries[el.first] = !spec_queries[el.first];
            } else {
                if (!queries_w_flip2[u].count(el.first)) queries_w_flip2[u].insert({el.first, el.second});
                else {
                    spec_queries.insert({el.first, false});
                    flip_path[el.first].push_back({el.second, u}); flip_path[el.first].push_back({queries_w_flip2[u][el.first], u});
                    queries_w_flip2[u].erase(el.first);
                }
            }
        }    
    }
 
    for (pib el : spec_queries) {
        if (!queries_w_flip2[u].count(el.first)) continue;
        spec_queries[el.first] = !spec_queries[el.first];
        flip_path[el.first].push_back({queries_w_flip2[u][el.first], u});
        queries_w_flip2[u].erase(el.first);
    }
    for (pib el : spec_queries) 
        if (el.second) queries_w_flip2[u][el.first] = u;
}
void precomp3() {
    dfs3(root);
    for (pii el : queries_w_flip2[root])
        flip_path[el.first].push_back({el.second, 0});
}
 
int main() {
    // freopen("spring.in", "r", stdin);
    // freopen("spring.out", "w", stdout);
 
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= q; i++) {
        int s; cin >> s;
        for (int j = 1; j <= s; j++) {
            int u; cin >> u;
            upd[i].push_back(u);
        }
    }
 
    precomp1();
    init();
    for (int i = 1; i <= q; i++) precomp2(i);
    precomp3();
 
    for (int query = 1; query <= q; query++) {
        if (n_leaves[query] % 2 == 1) {
            cout << "-1" << '\n';
            continue;
        }
 
        int new_n_1s = tot_n_1s + extra_n_1s[query], new_n_0s = tot_n_0s;
        for (pii path : flip_path[query]) {
            int path_n_1s = n_1s[path.first] - n_1s[path.second], path_n_0s = n_0s[path.first] - n_0s[path.second];
            new_n_1s += path_n_0s - path_n_1s, new_n_0s += path_n_1s - path_n_0s;
        }
 
        int ans = new_n_1s + 2 * (new_n_0s - 1); assert(new_n_0s >= 1);
        cout << ans << '\n';
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22620 KB Output is correct
2 Correct 88 ms 33896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24060 KB Output is correct
2 Correct 24 ms 24284 KB Output is correct
3 Correct 56 ms 27772 KB Output is correct
4 Correct 73 ms 32624 KB Output is correct
5 Correct 94 ms 33748 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26056 KB Output is correct
2 Correct 41 ms 26060 KB Output is correct
3 Correct 91 ms 53560 KB Output is correct
4 Correct 126 ms 64524 KB Output is correct
5 Correct 87 ms 50256 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31060 KB Output is correct
2 Correct 43 ms 27740 KB Output is correct
3 Correct 20 ms 24060 KB Output is correct
4 Correct 21 ms 25948 KB Output is correct
5 Correct 31 ms 26456 KB Output is correct
6 Correct 59 ms 32320 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 48256 KB Output is correct
2 Correct 121 ms 41272 KB Output is correct
3 Correct 109 ms 36888 KB Output is correct
4 Correct 123 ms 41812 KB Output is correct
5 Correct 120 ms 41356 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 57408 KB Output is correct
2 Correct 174 ms 60000 KB Output is correct
3 Correct 258 ms 71008 KB Output is correct
4 Correct 216 ms 69900 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22620 KB Output is correct
2 Correct 88 ms 33896 KB Output is correct
3 Correct 24 ms 24060 KB Output is correct
4 Correct 24 ms 24284 KB Output is correct
5 Correct 56 ms 27772 KB Output is correct
6 Correct 73 ms 32624 KB Output is correct
7 Correct 94 ms 33748 KB Output is correct
8 Correct 29 ms 26056 KB Output is correct
9 Correct 41 ms 26060 KB Output is correct
10 Correct 91 ms 53560 KB Output is correct
11 Correct 126 ms 64524 KB Output is correct
12 Correct 87 ms 50256 KB Output is correct
13 Correct 54 ms 31060 KB Output is correct
14 Correct 43 ms 27740 KB Output is correct
15 Correct 20 ms 24060 KB Output is correct
16 Correct 21 ms 25948 KB Output is correct
17 Correct 31 ms 26456 KB Output is correct
18 Correct 59 ms 32320 KB Output is correct
19 Correct 137 ms 48256 KB Output is correct
20 Correct 121 ms 41272 KB Output is correct
21 Correct 109 ms 36888 KB Output is correct
22 Correct 123 ms 41812 KB Output is correct
23 Correct 120 ms 41356 KB Output is correct
24 Correct 211 ms 57408 KB Output is correct
25 Correct 174 ms 60000 KB Output is correct
26 Correct 258 ms 71008 KB Output is correct
27 Correct 216 ms 69900 KB Output is correct
28 Correct 112 ms 39896 KB Output is correct
29 Correct 144 ms 46268 KB Output is correct
30 Correct 88 ms 34004 KB Output is correct
31 Correct 148 ms 65012 KB Output is correct
32 Correct 129 ms 41300 KB Output is correct
33 Correct 162 ms 52204 KB Output is correct
34 Correct 183 ms 56408 KB Output is correct
35 Correct 184 ms 56144 KB Output is correct