Submission #885185

#	Time	Username	Problem	Language	Result	Execution time	Memory
885185		SkillIssueWAGuy	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	140 ms	33172 KiB

cleaning

#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};
        }
    }
    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 (stderr)

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