oj.uz

Submission #1049178

# Submission time Handle Problem Language Result Execution time Memory
1049178 2024-08-08T14:29:24 Z Blagoj Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 153 ms 24872 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e5 + 100;

int cnt[mxn], prf[mxn][2], ans, tin[mxn], Time, dpt[mxn], nxt[mxn][19];
vector<int> g[mxn];

void dfs(int cur, int par = -1, int depth = 0) {
    if (par == -1) for (int i = 0; i < 19; i++) nxt[cur][i] = cur;
    else {
        nxt[cur][0] = par;
        for (int i = 1; i < 19; i++) nxt[cur][i] = nxt[nxt[cur][i - 1]][i - 1];
    }
    tin[cur] = Time++;
    dpt[cur] = depth;
    for (auto x : g[cur]) if (x != par) dfs(x, cur, depth + 1);
    if (g[cur].size() == 1) cnt[cur] = 1;
    for (auto x : g[cur]) if (x != par) cnt[cur] += cnt[x];
    if (par != -1) ans += 2 - (cnt[cur] % 2);
}

int LCA(int x, int y) {
    if (dpt[x] > dpt[y]) swap(x, y);
    for (int i = 18; i >= 0; i--) {
        if (dpt[y] - (1 << i) >= dpt[x]) y = nxt[y][i];
    }
    for (int i = 18; i >= 0; i--) {
        if (nxt[x][i] != nxt[y][i]) {
            x = nxt[x][i];
            y = nxt[y][i];
        }
    }
    if (x != y) x = nxt[x][0];
    return x;
}

void dfs1(int cur, int par) {
    prf[cur][0] = prf[par][0];
    prf[cur][1] = prf[par][1];
    prf[cur][cnt[cur] % 2]++;
    for (auto x : g[cur]) if (x != par) dfs1(x, cur);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int f, t;
        cin >> f >> t;
        g[f].push_back(t);
        g[t].push_back(f);
    }
    int root = -1;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 1) {
            root = i;
            break;
        }
    }
    dfs(root);
    dfs1(root, root);
    int leafs = 0;
    for (int i = 1; i <= n; i++) leafs += g[i].size() == 1;
    vector<int> sum(n + 1), par(n + 1);
    while (q--) {
        int sz;
        cin >> sz;
        vector<int> nodes(sz);
        for (int i = 0; i < sz; i++) cin >> nodes[i];
        sort(all(nodes), [&] (int a, int b) {
            return tin[a] < tin[b];
        });
        int total = leafs + sz;
        for (int i = 0; i < sz; i++) {
            if (i == 0 || nodes[i] != nodes[i - 1]) {
                if (g[nodes[i]].size() == 1) {
                    total--;
                    sum[nodes[i]]--;
                }
            }
        }
        vector<int> v;
        for (int i = 0; i < sz; i++) {
            v.push_back(nodes[i]);
            if (i) v.push_back(LCA(nodes[i - 1], nodes[i]));
        }
        sort(all(v));
        v.erase(unique(all(v)), v.end());
        sort(all(v), [&] (int a, int b) {
            return tin[a] < tin[b];
        });
        vector<int> s = {root};
        for (int i = 0; i < v.size(); i++) {
            while (LCA(s.back(), v[i]) != s.back()) s.pop_back();
            par[v[i]] = s.back();
            s.push_back(v[i]);
        }
        for (int i = 0; i < sz; i++) sum[nodes[i]]++;
        for (int i = v.size() - 1; i >= 0; i--) {
            if (v[i] == root) continue;
            sum[par[v[i]]] += sum[v[i]];
        }
        int newAns = ans + sz;
        for (int i = 0; i < v.size(); i++) {
            if (sum[v[i]] % 2 == 1) {
                ll c0 = prf[v[i]][0] - prf[par[v[i]]][0];
                ll c1 = prf[v[i]][1] - prf[par[v[i]]][1];
                newAns -= c0;
                newAns += c1;
            }
        }
        if (total % 2 == 1) cout << -1 << endl;
        else cout << newAns << endl;
        for (auto x : v) sum[x] = 0;
    }
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
cleaning.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 72 ms 6048 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6364 KB Output is correct
2 Correct 16 ms 6364 KB Output is correct
3 Correct 25 ms 16536 KB Output is correct
4 Correct 54 ms 14512 KB Output is correct
5 Correct 57 ms 17996 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6868 KB Output is correct
2 Correct 16 ms 6868 KB Output is correct
3 Correct 29 ms 23728 KB Output is correct
4 Correct 57 ms 23352 KB Output is correct
5 Correct 43 ms 21588 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6492 KB Output is correct
2 Correct 32 ms 6232 KB Output is correct
3 Correct 9 ms 5980 KB Output is correct
4 Correct 7 ms 6744 KB Output is correct
5 Correct 12 ms 6744 KB Output is correct
6 Correct 38 ms 6952 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12760 KB Output is correct
2 Correct 77 ms 12784 KB Output is correct
3 Correct 67 ms 9528 KB Output is correct
4 Correct 83 ms 13992 KB Output is correct
5 Correct 89 ms 14088 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16724 KB Output is correct
2 Correct 71 ms 19268 KB Output is correct
3 Correct 96 ms 19424 KB Output is correct
4 Correct 93 ms 18768 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 72 ms 6048 KB Output is correct
3 Correct 17 ms 6364 KB Output is correct
4 Correct 16 ms 6364 KB Output is correct
5 Correct 25 ms 16536 KB Output is correct
6 Correct 54 ms 14512 KB Output is correct
7 Correct 57 ms 17996 KB Output is correct
8 Correct 16 ms 6868 KB Output is correct
9 Correct 16 ms 6868 KB Output is correct
10 Correct 29 ms 23728 KB Output is correct
11 Correct 57 ms 23352 KB Output is correct
12 Correct 43 ms 21588 KB Output is correct
13 Correct 55 ms 6492 KB Output is correct
14 Correct 32 ms 6232 KB Output is correct
15 Correct 9 ms 5980 KB Output is correct
16 Correct 7 ms 6744 KB Output is correct
17 Correct 12 ms 6744 KB Output is correct
18 Correct 38 ms 6952 KB Output is correct
19 Correct 38 ms 12760 KB Output is correct
20 Correct 77 ms 12784 KB Output is correct
21 Correct 67 ms 9528 KB Output is correct
22 Correct 83 ms 13992 KB Output is correct
23 Correct 89 ms 14088 KB Output is correct
24 Correct 74 ms 16724 KB Output is correct
25 Correct 71 ms 19268 KB Output is correct
26 Correct 96 ms 19424 KB Output is correct
27 Correct 93 ms 18768 KB Output is correct
28 Correct 71 ms 13788 KB Output is correct
29 Correct 80 ms 21072 KB Output is correct
30 Correct 63 ms 19248 KB Output is correct
31 Correct 49 ms 24872 KB Output is correct
32 Correct 106 ms 14076 KB Output is correct
33 Correct 92 ms 17588 KB Output is correct
34 Correct 110 ms 21056 KB Output is correct
35 Correct 153 ms 20980 KB Output is correct