oj.uz

Submission #885182

# Submission time Handle Problem Language Result Execution time Memory
885182 2023-12-09T07:40:34 Z SkillIssueWAGuy Spring cleaning (CEOI20_cleaning) C++14
54 / 100
 102 ms 34120 KB 
#include<vector>
#include<iostream>
#include<utility>
#include<algorithm>
#include<cmath>
using namespace std;
namespace fake{
    std::vector<std::vector<int>> tree;
    std::vector<int> incount, dp, flips, normals, full, parent;
    void setup(int n){
        tree = std::vector<std::vector<int>>(n, std::vector<int>(0));
        dp = parent = std::vector<int>(n, -1);
        incount = std::vector<int>(n, 0);
    }
    void dfs(int node){
        if (tree[node].size() == 0){
            dp[node] = 1;
            if (incount[node] == -1){
                dp[node] = 0;
            }
            return;
        }
        dp[node] = 0;
        for (int i : tree[node]){
            dfs(i);
            dp[node] += dp[i];
        }
        dp[node] %= 2;
        if (incount[node] == -2){
            dp[node] = 1 - dp[node];
        }
        return;
    }
}
vector<vector<int>> tree;
vector<vector<pair<int,int>>> bptrs;
vector<int> dp, dfsorder, dfspos, input, depth, parent, tsize;
vector<bool> isleaf;
int N, Q, D, logN, output, lcount, root;
void dfs(int node){
    dfspos[node] = dfsorder.size();
    dfsorder.push_back(node);
    tsize[node] = 1;
    if (isleaf[node]){
        dp[node] = 1;
        return;
    }
    dp[node] = 0;
    for (int i : tree[node]){
        if (depth[i] == -1){
            depth[i] = depth[node] + 1;
            parent[i] = node;
            dfs(i);
            dp[node] += dp[i];
            tsize[node] += tsize[i];
        }
    }
    dp[node] %= 2;
    return;
}
bool Comp(int a, int b){
    return dfspos[a] < dfspos[b];
}
pair<int,int> LCA(int a, int b){
    int out = 0;
    if (depth[a] < depth[b]){
        int c = a;
        a = b;
        b = c;
    }
    for (int j = logN-1; j >= 0; j--){
        if (depth[bptrs[j][a].first] >= depth[b]){
            out += bptrs[j][a].second;
            a = bptrs[j][a].first;
        }
    }
    if (a == b){
        return {a, out};
    }
    for (int j = logN-1; j >= 0; j--){
        if (bptrs[j][a].first != bptrs[j][b].first){
            out += bptrs[j][a].second + bptrs[j][b].second;
            a = bptrs[j][a].first;
            b = bptrs[j][b].first;
        }
    }
    out += bptrs[0][a].second + bptrs[0][b].second;
    return {bptrs[0][a].first, out};
}
int docase(){
    int out = output + input.size(), lnew;
    for (int i : input){
        if (fake::full.size() == 0){
            fake::full.push_back(i);
        }
        else if (fake::full.back() != i){
            fake::full.push_back(i);
        }
        fake::incount[i] ++;
    }
    for (int i : fake::full){
        if ((fake::incount[i] % 2 == 1) != isleaf[i]){
            fake::flips.push_back(i);
            fake::incount[i] = -2;
        }
        else {
            fake::incount[i] = 0;
        }
    }
    if (!fake::incount[root]){
        fake::normals.push_back(root);
        fake::full.push_back(root);
        fake::incount[root] = -1;
    }
    if (fake::flips.size() > 1){
        for (int i = 0; i < fake::flips.size() - 1; i++){
            int a = LCA(fake::flips[i], fake::flips[i+1]).first;
            if (!fake::incount[a]){
                fake::incount[a] = -1;
                fake::normals.push_back(a);
            }
        }
    }
    fake::full.clear();
    for (int i : fake::flips){
        fake::full.push_back(i);
    }
    for (int i : fake::normals){
        fake::full.push_back(i);
    }
    sort(fake::full.begin(), fake::full.end(), Comp);
    // make the tree
    fake::parent[root] = root;
    int cur = root;
    for (int i : fake::full){
        while (dfspos[i] > dfspos[cur] + tsize[cur] - 1){
            cur = fake::parent[cur];
        }
        fake::parent[i] = cur;
        if (cur != i){
            fake::tree[cur].push_back(i);
        }
        cur = i;
    }
    fake::dfs(root);
    if (dp[root] != fake::dp[root]){
        out = -1;
    }
    else {
        for (int i : fake::full){
            if (fake::dp[i] == 1){
                out += LCA(i, fake::parent[i]).second;
            }
        }
    }
    // finish
    for (int i : fake::full){
        fake::incount[i] = 0;
        fake::tree[i].clear();
        fake::dp[i] = -1;
        fake::parent[i] = -1;
    }
    fake::full.clear();
    fake::flips.clear();
    fake::normals.clear();
    return out;
}
int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> Q;
    output = lcount = 0;
    logN = ceil(log2(N)) + 2;
    tree = vector<vector<int>>(N, vector<int>(0));
    isleaf = vector<bool>(N, false);
    bptrs = vector<vector<pair<int,int>>>(logN, vector<pair<int,int>>(N, {0,0}));
    tsize = parent = dp = dfspos = depth = vector<int>(N, -1);
    fake::setup(N);
    for (int i = 0; i < N-1; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    root = -1;
    for (int i = 0; i < N; i++){
        if (tree[i].size() == 1){
            isleaf[i] = true;
            lcount ++;
        }
        else if (root == -1){
            root = i;
        }
    }
    depth[root] = 0;
    parent[root] = root;
    dfs(root);
    for (int i = 0; i < N; i++){
        bptrs[0][i] = {parent[i], -1 + 2 * dp[i]};
        output += 2 - dp[i];
    }
    bptrs[0][root] = {root, 0};
    output -= 2 - dp[root];
    for (int i = 1; i < logN; i++){
        for (int j = 0; j < N; j++){
            bptrs[i][j] = {bptrs[i-1][bptrs[i-1][j].first].first, bptrs[i-1][j].second + bptrs[i-1][bptrs[i-1][j].first].second};
        }
    }
    bptrs[0][0] = {0, 0};
    for (int i = 0; i < Q; i++){
        input = {};
        cin >> D;
        int v;
        for (int j = 0; j < D; j++){
            cin >> v;
            v--;
            input.push_back(v);
        }
        sort(input.begin(), input.end(), Comp);
        cout << docase() << '\n';;
    }
    return 0;
}

Compilation message

cleaning.cpp: In function 'int docase()':
cleaning.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int i = 0; i < fake::flips.size() - 1; i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:91:38: warning: unused variable 'lnew' [-Wunused-variable]
   91 |     int out = output + input.size(), lnew;
      |                                      ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 33 ms 6320 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2028 KB Output is correct
2 Correct 13 ms 2028 KB Output is correct
3 Correct 34 ms 28236 KB Output is correct
4 Correct 52 ms 21104 KB Output is correct
5 Correct 59 ms 29252 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3388 KB Output is correct
2 Correct 14 ms 2776 KB Output is correct
3 Correct 44 ms 34120 KB Output is correct
4 Correct 61 ms 33116 KB Output is correct
5 Correct 45 ms 31212 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7052 KB Output is correct
2 Correct 17 ms 5816 KB Output is correct
3 Correct 8 ms 5820 KB Output is correct
4 Correct 9 ms 6076 KB Output is correct
5 Correct 11 ms 6336 KB Output is correct
6 Incorrect 28 ms 6576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18900 KB Output is correct
2 Correct 68 ms 18764 KB Output is correct
3 Correct 40 ms 9560 KB Output is correct
4 Correct 66 ms 18772 KB Output is correct
5 Correct 68 ms 18724 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 29688 KB Output is correct
2 Correct 71 ms 31916 KB Output is correct
3 Correct 85 ms 31904 KB Output is correct
4 Correct 80 ms 31556 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 33 ms 6320 KB Output is correct
3 Correct 12 ms 2028 KB Output is correct
4 Correct 13 ms 2028 KB Output is correct
5 Correct 34 ms 28236 KB Output is correct
6 Correct 52 ms 21104 KB Output is correct
7 Correct 59 ms 29252 KB Output is correct
8 Correct 17 ms 3388 KB Output is correct
9 Correct 14 ms 2776 KB Output is correct
10 Correct 44 ms 34120 KB Output is correct
11 Correct 61 ms 33116 KB Output is correct
12 Correct 45 ms 31212 KB Output is correct
13 Correct 33 ms 7052 KB Output is correct
14 Correct 17 ms 5816 KB Output is correct
15 Correct 8 ms 5820 KB Output is correct
16 Correct 9 ms 6076 KB Output is correct
17 Correct 11 ms 6336 KB Output is correct
18 Incorrect 28 ms 6576 KB Output isn't correct
19 Halted 0 ms 0 KB -