제출 #342749

#제출 시각아이디문제언어결과실행 시간메모리
342749urd05Spring cleaning (CEOI20_cleaning)C++14
9 / 100
313 ms26860 KiB
#include <bits/stdc++.h> using namespace std; const int s=131072; int seg[s*2]; int lazy[s*2]; void propagate(int node,int nodel,int noder) { if (lazy[node]) { seg[node]=noder-nodel+1-seg[node]; if (node<s) { lazy[node*2]^=1; lazy[node*2+1]^=1; } lazy[node]=0; } } int sum(int l,int r,int node=1,int nodel=0,int noder=s-1) { propagate(node,nodel,noder); 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 l,int r,int node=1,int nodel=0,int noder=s-1) { propagate(node,nodel,noder); if (r<nodel||l>noder) { return; } if (l<=nodel&&noder<=r) { lazy[node]^=1; propagate(node,nodel,noder); return; } int mid=(nodel+noder)/2; update(l,r,node*2,nodel,mid); update(l,r,node*2+1,mid+1,noder); seg[node]=seg[node*2]+seg[node*2+1]; } 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 top[100000]; 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 (leaf[v]%2==0) got--; else got++; return dp[v]=got; } void dfs(int v,int prev) { p[v]=prev; 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]; if (sz[son[v][0]]<sz[nt]) { swap(son[v][0],son[v][son[v].size()-1]); } } } void dfs_hld(int v) { ind[v]=f++; for(int i=0;i<son[v].size();i++) { int nt=son[v][i]; top[nt]=(i==0?top[v]:nt); dfs_hld(nt); } } 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); top[r]=r; dfs_hld(r); int ori=0; for(int i=0;i<n;i++) { 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<n;i++) { if (i!=r) { seg[i+s]=(leaf[i]%2==0?1:0); } } for(int i=s-1;i>0;i--) { seg[i]=seg[i*2]+seg[i*2+1]; } for(int i=0;i<q;i++) { int k; vector<int> save0; scanf("%d",&k); int ret=n-1+k; vector<int> save; int l=leaf[r]; for(int j=0;j<k;j++) { int v; scanf("%d",&v); v--; save0.push_back(v); if (!son[v].empty()||cnt[v]>0) { save.push_back(v); l++; } cnt[v]++; } if (l%2!=0) { printf("-1\n"); for(int j=0;j<save0.size();j++) { cnt[save0[j]]--; } continue; } sort(save.begin(),save.end(),comp); reverse(save.begin(),save.end()); for(int j=0;j<save.size();j++) { int now=save[j]; while (now!=-1) { update(ind[top[save[j]]],ind[save[j]]); now=p[top[now]]; } update(0,0); } printf("%d\n",ret+sum(0,s-1)); for(int j=0;j<save.size();j++) { int now=save[j]; while (now!=-1) { update(ind[top[save[j]]],ind[save[j]]); now=p[top[now]]; } update(0,0); } for(int j=0;j<save0.size();j++) { cnt[save0[j]]--; } } }

컴파일 시 표준 에러 (stderr) 메시지

cleaning.cpp: In function 'int getleaf(int)':
cleaning.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs_hld(int)':
cleaning.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         for(int j=0;j<son[rev[i]].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:191:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |             for(int j=0;j<save0.size();j++) {
      |                         ~^~~~~~~~~~~~~
cleaning.cpp:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:207:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:215:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |         for(int j=0;j<save0.size();j++) {
      |                     ~^~~~~~~~~~~~~
cleaning.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  174 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:180:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  180 |             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...