Submission #1235209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235209		t_holl	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	176 ms	45480 KiB

cleaning

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 1e18;

vector<int> vp;
vector<vector<int>> roads;

int res = 0;

vector<int> cost;
vector<int> cost_prefix;
vector<int> rcost_prefix;
vector<int> parents, subsize;
vector<int> depth, inv_postorder;
int postorder_cnt = 0;
vector<vector<int>> parents_2k;

int compute (int node, int parent) {
    int cnt = 0;
    for (int next : roads[node]) if (next != parent)
        cnt += compute(next, node);
    if (cnt == 0) cnt ++;

    if ((cnt & 1) == 0) cost[node] ++;
    cost[node] ++;
    if (parent == -1) cost[node] = 0;

    return cnt;
}
void dfs (int node, int parent, int _depth = 0) {
    cost_prefix[node]  = cost[node];
    rcost_prefix[node] = parent == -1 ? 0 : 3 - cost[node];
    depth[node] = _depth;
    subsize[node] = 1;
    if (parent != -1) {
         cost_prefix[node] +=  cost_prefix[parent];
        rcost_prefix[node] += rcost_prefix[parent];

        parents[node] = parent;
    }
    
    for (int next : roads[node]) if (next != parent) {
        dfs(next, node, _depth + 1);
        subsize[node] += subsize[next];
    }
    
    inv_postorder[node] = postorder_cnt ++;
}
const int MAXK = 19;
void init_lca (int N) {
    parents_2k.resize(N, vector<int>(MAXK, - 1));

    for (int i = 0; i < N; i ++)
        parents_2k[i][0] = parents[i];
    
    for (int k = 1; k < MAXK; k ++) {
        for (int i = 0; i < N; i ++) {
            if (parents_2k[i][k - 1] == -1) continue ;

            parents_2k[i][k] = parents_2k[parents_2k[i][k - 1]][k - 1];
        }
    }
}
int jump (int node, int count) {
    for (int k = 0; k < MAXK; k ++)
        if ((1 << k) & count)
            node = parents_2k[node][k];
    return node;
}

int lca (int a, int b) {
    if (depth[a] > depth[b]) swap (a, b);

    b = jump(b, depth[b] - depth[a]);
    if (a == b) return a;

    for (int k = MAXK - 1; k >= 0; k --) {
        if (parents_2k[a][k] == parents_2k[b][k]) continue ;

        a = parents_2k[a][k];
        b = parents_2k[b][k];
    }

    return parents[a];
}

struct VirtualTree {
    vector<vector<int>> vroads;

    map<int, int> id_to_vid;
    vector<int> vid_to_id;
    vector<int> cnt_id;

    VirtualTree (vector<int> nodes) {
        {
            vector<pair<int, int>> tnodes;
            for (int u : nodes)
                tnodes.push_back({ inv_postorder[u], u });
            
            sort(tnodes.begin(), tnodes.end());

            set<int> doub_vid_to_id;
            for (int u : nodes)
                doub_vid_to_id.insert(u);
            for (int i = 0; i + 1 < nodes.size(); i ++) {
                doub_vid_to_id.insert(
                    lca( tnodes[i].second, tnodes[i + 1].second )
                );
            }
            for (int u : doub_vid_to_id)
                vid_to_id.push_back(u);
            for (int i = 0; i < vid_to_id.size(); i ++)
                id_to_vid[vid_to_id[i]] = i;
            
            cnt_id.resize(id_to_vid.size());
            for (int u : nodes)
                cnt_id[id_to_vid[u]] = 1;
        }
        {
            vector<pair<pair<int, int>, int>> vnodes;
            int i = 0;
            for (int u : vid_to_id)
                vnodes.push_back({ {inv_postorder[u], subsize[u]}, i ++ });
            sort(vnodes.begin(), vnodes.end());

            vroads.resize(vnodes.size());
            stack<pair<int, int>> vs;
            for (auto vn : vnodes) {
                int begin = vn.first.first - vn.first.second + 1;
                while (vs.size() != 0 && vs.top().first >= begin) {
                    int a = vn.second;
                    int b = vs.top().second;

                    vroads[a].push_back(b);
                    vroads[b].push_back(a);
                    vs.pop();
                }

                vs.push({ vn.first.first, vn.second });
            }
        }
    }

    vector<pair<int, int>> ret_roads;
    int ret_cnt;
    vector<pair<int, int>> dfs (int root) {
        ret_roads.clear();

        _dfs(id_to_vid[root], -1);

        return ret_roads;
    }
    int _dfs (int node, int parent) {
        int cnt = 0;

        for (int next : vroads[node]) if (next != parent) {
            cnt += _dfs(next, node);
        }

        cnt += cnt_id[node];
        if ((cnt & 1) == 1 && parent != -1) {
            ret_roads.push_back({ vid_to_id[node], vid_to_id[parent] });
        }

        return cnt;
    }
};

int res_before;
int root;
int leaf;
int solve (vector<int> &deg, vector<int> &points) {
    int res = res_before + points.size();
    int nleaf = leaf + points.size();

    map<int, int> pc;
    for (int u : points)
        pc[u] = pc[u] + 1;
    
    points.clear();
    for (auto v : pc) {
        int node = v.first;
        int cnt  = v.second;

        if (deg[node] == 1) {
            cnt --;
            nleaf --;
        }

        if ((cnt & 1) == 1) {
            points.push_back(node);
        }
    }

    if ((nleaf & 1) == 1) return -1;

    points.push_back(root);

    VirtualTree tree(points);
    vector<pair<int, int>> roads = tree.dfs(root);

    for (auto u : roads) {
        res += rcost_prefix[u.first] - rcost_prefix[u.second];
        res -=  cost_prefix[u.first] -  cost_prefix[u.second];
    }
    return res;
}

void solve () {
    int N, Q; cin >> N >> Q;

    vp.resize(N);
    roads.resize(N);
    cost .resize(N);
    cost_prefix.resize(N);
    rcost_prefix.resize(N);
    parents.resize(N);
    depth.resize(N);
    subsize.resize(N);
    inv_postorder.resize(N);

    vector<int> deg(N);

    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        roads[a].push_back(b);
        roads[b].push_back(a);
        deg[a] ++; deg[b] ++;
    }

    root = 0;
    for (; root < N; root ++)
        if (deg[root] != 1)
            break ;
    
    compute(root, -1);
    dfs(root, -1);
    init_lca(N);

    res_before = 0;
    for (int u : cost)
        res_before += u;
    leaf = 0;
    for (int u : deg) if (u == 1)
        leaf ++;
    
    for (int i = 0; i < Q; i ++) {
        int d;
        cin >> d;
        
        vector<int> points(d);
        for (int &x : points) {
            cin >> x;
            x --;
        }
        
        int res = solve(deg, points);

        cout << res << "\n";
    }
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

• 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