Submission #977055

#	Time	Username	Problem	Language	Result	Execution time	Memory
977055		DAleksa	Spring cleaning (CEOI20_cleaning)	C++17	0 / 100	61 ms	18256 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, LOG = 17;
int n, q;
vector<int> g[N], fake[N];
int timer, tin[N], tout[N];
int up[N][LOG];
int cnt[N], even[N], odd[N];
int dep[N];
int root;
bool mark[N];

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int LCA(int u, int v) {
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = LOG - 1; j >= 0; j--) {
        if(up[u][j] == 0) continue;
        if(is_ancestor(up[u][j], v)) continue;
        u = up[u][j];
    }
    return up[u][0];
}

int ans;

void dfs(int u, int par) {
    if(g[u].size() == 1) cnt[u]++;
    tin[u] = ++timer;
    for(int v : g[u]) {
        if(v == par) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        up[v][0] = u;
        cnt[u] += cnt[v];
    }
    tout[u] = ++timer;
}

void dfs2(int u, int par) {
    if(cnt[u] % 2 == 0) {
        even[u]++;
        ans++;
    } else odd[u]++;
    for(int v : g[u]) {
        if(v == par) continue;
        even[v] = even[u];
        odd[v] = odd[u];
        dfs2(v, u);
    }
}

int sz[N];
int add;

void fdfs(int u, int par) {
    sz[u] = 1;
    for(int v : fake[u]) {
        fdfs(v, u);
        sz[u] ^= sz[v];
        if(sz[v] == 1) {
            add -= even[v] - even[u];
            add += odd[v] - odd[u];
        }
    }
}

void clr(int u, int par) {
    for(int v : fake[u]) clr(v, u);
    fake[u].clear();
    mark[u] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        if(g[i].size() > 1) {
            root = i;
            break;
        }
    }
    int leaves = 0;
    for(int i = 1; i <= n; i++) leaves += (g[i].size() == 1);
    dfs(root, 0);
    dfs2(root, 0);
    for(int j = 1; j < LOG; j++) for(int i = 1; i <= n; i++) up[i][j] = up[up[i][j - 1]][j - 1];
//    cout << ans << "\n";

    while(q--) {
        int m;
        cin >> m;
        vector<int> all;
        int more = 0;
        map<int, int> mp;
        for(int i = 0; i < m; i++) {
            int x;
            cin >> x;
            mp[x]++;
        }
        for(pair<int, int> p : mp) {
            if(p.second % 2 != (g[p.first].size() == 1)) {
                all.push_back(p.first);
                more++;
            }
        }
        if((leaves + more) % 2 == 1) {
            cout << "-1\n";
            continue;
        }
        vector<int> nw;
        while(all.size() > 0) {
            sort(all.begin(), all.end(), [&](int u, int v) { return tout[u] < tout[v]; });
            nw.clear();
            for(int i = 0; i < all.size(); i++) {
                int u = all[i];
                int par = root;
                if(i > 0) par = LCA(all[i - 1], all[i]);
                if(i < all.size() - 1) {
                    int lca = LCA(all[i], all[i + 1]);
                    if(dep[lca] > dep[par]) par = lca;
                }
                if(par == u) continue;
                fake[par].push_back(u);
                mark[u] = true;
                nw.push_back(par);
            }
            all.clear();
            for(int i = 0; i < nw.size(); i++) {
                if(mark[nw[i]]) continue;
                all.push_back(nw[i]);
            }
        }
        add = 0;
//        for(int i = 1; i <= n; i++) {
//            cout << i << ": ";
//            for(int j : fake[i]) cout << j << " ";
//            cout << "\n";
//        }
        fdfs(root, 0);
        cout << n - 2 + m + ans + add << "\n";
        clr(root, 0);
    }
    return 0;
}

/*

8 1
1 2
1 3
1 4
2 5
2 6
3 7
4 8
2 7 7

*/

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:124:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for(int i = 0; i < all.size(); i++) {
      |                            ~~^~~~~~~~~~~~
cleaning.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 if(i < all.size() - 1) {
      |                    ~~^~~~~~~~~~~~~~~~
cleaning.cpp:138:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             for(int i = 0; i < nw.size(); i++) {
      |                            ~~^~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30