Submission #342487

#	Time	Username	Problem	Language	Result	Execution time	Memory
342487		benedict0724	Spring cleaning (CEOI20_cleaning)	C++17	0 / 100	1096 ms	7916 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> adj[100002];
int leaf[100002];
int deg[100002];
int par[100002];
bool check[100002];
bool pos;
int dp[100002];
ll ans = 0;
void dfs(int x, int p){
    dp[x] = leaf[x];
    for(auto u : adj[x]){
        if(u != p){
            par[u] = x;
            dfs(u, x);
            dp[x] += dp[u];
        }
    }

    if(dp[x] == 0){
        dp[x] = 1;
        return;
    }
    if(dp[x]%2){
        ans += dp[x];
        dp[x] = 1;
        return;
    }
    ans += dp[x];
    dp[x] = 2;
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i=1;i<n;i++){
        int s, e;
        scanf("%d %d", &s, &e);
        adj[s].push_back(e);
        adj[e].push_back(s);
        deg[s]++;
        deg[e]++;
    }
    pos = true;
    for(int i=1;i<=n;i++){
        if(deg[i] == 1) pos = !pos;
    }

    dfs(1, -1);

    for(int i=1;i<=q;i++){
        int d;
        scanf("%d", &d);
        vector<int> v;
        for(int i=1;i<=d;i++){
            int k;
            scanf("%d", &k);
            check[k] = false;
            bool change = true;
            if(deg[k] == 1){
                ans++;
                deg[k]++;
                change = false;
                check[k] = true;
            }
            else pos = !pos;
            v.push_back(k);

            if(change) while(k != 1){
                if(dp[k] == 1){
                    ans++;
                    dp[k] = 2;
                }
                else{
                    ans--;
                    dp[k] = 1;
                }
                k = par[k];
            }
        }

        if(pos) printf("%lld\n", ans);
        else printf("-1\n");

        for(auto k : v){
            if(check[k]){
                deg[k]--;
                ans--;
            }
            else{
                while(k != 1){
                    if(dp[k] == 1){
                        ans++;
                        dp[k] = 2;
                    }
                    else{
                        ans--;
                        dp[k] = 1;
                    }
                    k = par[k];
                }
            }
            pos = !pos;
        }
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d %d", &s, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%d", &d);
      |         ~~~~~^~~~~~~~~~
cleaning.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~

• 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