Submission #342482

#	Time	Username	Problem	Language	Result	Execution time	Memory
342482		urd05	Spring cleaning (CEOI20_cleaning)	C++14	0 / 100	149 ms	12524 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

int deg[100000];
vector<int> adj[100000];
vector<int> son[100000];
int leaf[100000];
int p[100000];
int dp[100000];
const int nn=-1e9;

int getleaf(int v) {
    if (leaf[v]!=-1) {
        return leaf[v];
    }
    if (son[v].empty()) {
        return leaf[v]=1;
    }
    leaf[v]=0;
    for(int i=0;i<son[v].size();i++) {
        leaf[v]+=getleaf(son[v][i]);
    }
    return leaf[v];
}

int ans(int v) {
    if (dp[v]!=nn) {
        return dp[v];
    }
    if (p[v]==-1) {
        if (getleaf(v)%2==0) {
            return -1;
        }
        else {
            return 1;
        }
    }
    int got=ans(p[v]);
    if (getleaf(p[v])%2!=getleaf(v)%2) {
        got=-got;
    }
    if (getleaf(v)%2==0) {
        got--;
    }
    else {
        got++;
    }
    return dp[v]=got;
}

void dfs(int v,int prev) {
    p[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (prev==nt) {
            continue;
        }
        son[v].push_back(nt);
        dfs(nt,v);
    }
}

int cnt[100000];

int main(void) {
    int n,q;
    scanf("%d %d",&n,&q);
    memset(leaf,-1,sizeof(leaf));
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        deg[u]++;
        deg[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int r=0;
    for(int i=0;i<n;i++) {
        dp[i]=nn;
        p[i]=-1;
        if (deg[i]!=1) {
            r=i;
        }
    }
    dfs(r,-1);
    int ori=0;
    for(int i=0;i<n;i++) {
        if (i!=r) {
            if (getleaf(i)%2==0) {
                ori++;
            }
        }
    }
    for(int i=0;i<q;i++) {
        int k;
        vector<int> save;
        scanf("%d",&k);
        int ret=ori;
        int l=getleaf(r);
        for(int i=0;i<k;i++) {
            int v;
            scanf("%d",&v);
            v--;
            if (son[v].empty()&&cnt[v]==0) {
                
            }
            else {
                if (cnt[v]%2==0) {
                    ret+=ans(v);
                }
                else {
                    ret-=ans(v);
                }
                l++;
            }
            cnt[v]++;
            save.push_back(v);
        }
        if (l%2!=0) {
            printf("-1\n");
        }
        else
            printf("%d\n",n-1+k+ret);
        for(int j=0;j<save.size();j++) {
            cnt[save[j]]--;
        }
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int getleaf(int)':
cleaning.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |             scanf("%d",&v);
      |             ~~~~~^~~~~~~~~

• 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