oj.uz

Submission #342487

# Submission time Handle Problem Language Result Execution time Memory
342487 2021-01-02T08:48:47 Z benedict0724 Spring cleaning (CEOI20_cleaning) C++17
0 / 100
 1000 ms 7916 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 4072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 4332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 5996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 7916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -