Submission #1043669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043669		myst6	Spring cleaning (CEOI20_cleaning)	C++14	70 / 100	1043 ms	22096 KiB

cleaning

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    // take inputs
    cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>> adj(2e5);
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // analyse tree
    vector<int> parent(2e5, -1);
    vector<int> depth(2e5, 0);
    vector<int> parity(2e5, 0);
    vector<int> cost(2e5, 0);
    set<int> upd;
    auto dfs = [&](auto &self, int x) -> void {
        for (int y : adj[x]) {
            if (y != parent[x]) {
                parent[y] = x;
                depth[y] = depth[x] + 1;
                self(self, y);
                parity[x] ^= parity[y];
                cost[x] += cost[y] + 1;
                if (parity[y] == 0) cost[x] += 1;
            }
        }
        if (adj[x].size() == 1) parity[x] ^= 1;
    };
    dfs(dfs, 0);
 
    // check for subtask 6
    bool subtask_6 = true;
    vector<vector<int>> queries(Q);
    for (int i=0; i<Q; i++) {
        int D;
        cin >> D;
        if (D != 1) subtask_6 = false;
        for (int j=0; j<D; j++) {
            int a;
            cin >> a;
            queries[i].push_back(a);
        }
    }
 
    if (subtask_6) {
        vector<int> n_odd(N), n_even(N);
        auto dfs = [&](auto &self, int x) -> void {
            if (parity[x] == 1) n_odd[x] += 1;
            if (parity[x] == 0) n_even[x] += 1;
            for (int y : adj[x]) {
                if (y != parent[x]) {
                    n_odd[y] += n_odd[x];
                    n_even[y] += n_even[x];
                    self(self, y);
                }
            }
        };
        dfs(dfs, 0);
        for (int i=0; i<Q; i++) {
            int x = queries[i][0];
            x--;
            if (adj[x].size() == 1) {
                if (parity[0] == 1) {
                    cout << "-1\n";
                } else {
                    cout << cost[0] + 1 << "\n";
                }
            } else {
                if (parity[0] == 0) {
                    cout << "-1\n";
                } else {
                    cout << cost[0] + n_odd[x] - n_even[x] << "\n";
                }
            }
        }
        return 0;
    }
 
    // handle queries
    for (int i=0; i<Q; i++) {
        set<pair<int,int>> upd;
        for (int j=0; j<queries[i].size(); j++) {
            int a = queries[i][j];
            a--;
            adj[a].push_back(N + j);
            parity[N + j] = 1;
            cost[N + j] = 0;
            upd.insert({depth[a], a});
        }
        set<pair<int,int>> upd_copy(upd);
        while (!upd.empty()) {
            auto it = prev(upd.end());
            int d = it->first, x = it->second;
            upd.erase(it);
            if (x == -1) continue;
            parity[x] = 0;
            cost[x] = 0;
            for (int y : adj[x]) {
                if (y != parent[x]) {
                    parity[x] ^= parity[y];
                    cost[x] += cost[y] + 1;
                    if (parity[y] == 0) cost[x] += 1;
                }
            }
            if (adj[x].size() == 1) parity[x] ^= 1;
            upd.insert({d - 1, parent[x]});
        }
        // if the root of the tree has odd parity, it is impossible to clean, otherwise output its cost
        if (parity[0] == 1) {
            cout << "-1\n";
        } else {
            cout << cost[0] << "\n";
        }
        if (i == Q - 1) continue; // no need to reverse changes on last query
        // reverse changes
        while (!upd_copy.empty()) {
            auto it = prev(upd_copy.end());
            int d = it->first, x = it->second;
            upd_copy.erase(it);
            if (x == -1) continue;
            while (adj[x].back() >= N) adj[x].pop_back();
            parity[x] = 0;
            cost[x] = 0;
            for (int y : adj[x]) {
                if (y != parent[x]) {
                    parity[x] ^= parity[y];
                    cost[x] += cost[y] + 1;
                    if (parity[y] == 0) cost[x] += 1;
                }
            }
            if (adj[x].size() == 1) parity[x] ^= 1;
            upd_copy.insert({d - 1, parent[x]});
        }
    }
 
    return 0;
}

Compilation message (stderr)

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

• 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: 0 / 30