Submission #342510

#TimeUsernameProblemLanguageResultExecution timeMemory
342510urd05Spring cleaning (CEOI20_cleaning)C++14
34 / 100
1094 ms24812 KiB
#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 ind[100000]; int f=0; int sz[100000]; int rev[100000]; int cnt[100000]; int psum[100001]; 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) { return 0; } int got=ans(p[v]); if (getleaf(v)%2==0) got--; else got++; return dp[v]=got; } void dfs(int v,int prev) { p[v]=prev; ind[v]=f++; sz[v]=1; 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); sz[v]+=sz[nt]; } } const int s=131072; int seg[s*2]; int sum(int l,int r,int node=1,int nodel=0,int noder=s-1) { if (r<nodel||l>noder) { return 0; } if (l<=nodel&&noder<=r) { return seg[node]; } int mid=(nodel+noder)/2; return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder); } void update(int i,int val) { i+=s; seg[i]+=val; while (i>1) { i/=2; seg[i]=seg[i*2]+seg[i*2+1]; } } bool comp(int a,int b) { return ind[a]<ind[b]; } 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; int l=0; for(int i=0;i<n;i++) { if (son[i].empty()) { l++; update(ind[i],1); } rev[ind[i]]=i; } for(int i=n-1;i>=0;i--) { if (son[rev[i]].empty()) { leaf[rev[i]]=1; continue; } leaf[rev[i]]=0; for(int j=0;j<son[rev[i]].size();j++) { leaf[rev[i]]+=leaf[son[rev[i]][j]]; } if (i&&leaf[rev[i]]%2==0) { ori++; } } for(int i=0;i<q;i++) { int k; vector<int> save0; scanf("%d",&k); int ret=n-1+k; vector<int> save; for(int j=0;j<k;j++) { int v; scanf("%d",&v); v--; save0.push_back(v); if (!son[v].empty()||cnt[v]>0) { update(ind[v],1); save.push_back(v); l++; } cnt[v]++; } if (l%2!=0) { printf("-1\n"); for(int j=0;j<save.size();j++) { update(ind[save[j]],-1); l--; } for(int j=0;j<save0.size();j++) { cnt[save0[j]]--; } continue; } for(int i=0;i<n;i++) { psum[i+1]=psum[i]+seg[s+i]; } for(int j=0;j<n;j++) { if (j!=r) { if ((psum[ind[j]+sz[j]]-psum[ind[j]])%2==0) { ret++; } } } printf("%d\n",ret); for(int j=0;j<save.size();j++) { update(ind[save[j]],-1); l--; } for(int j=0;j<save0.size();j++) { cnt[save0[j]]--; } } }

Compilation message (stderr)

cleaning.cpp: In function 'int getleaf(int)':
cleaning.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int j=0;j<son[rev[i]].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for(int j=0;j<save.size();j++) {
      |                         ~^~~~~~~~~~~~
cleaning.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for(int j=0;j<save0.size();j++) {
      |                         ~^~~~~~~~~~~~~
cleaning.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for(int j=0;j<save0.size();j++) {
      |                     ~^~~~~~~~~~~~~
cleaning.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |             scanf("%d",&v);
      |             ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...