제출 #808783

#제출 시각아이디문제언어결과실행 시간메모리
808783DJeniUpSpring cleaning (CEOI20_cleaning)C++17
9 / 100
277 ms24360 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") using namespace std; typedef int ll; typedef unsigned long long ull; typedef pair<ll,ll>pairll; typedef pair<ll,ull>pairull; typedef pair<ll,pairll>pair3l; typedef long double ld; typedef pair<ld,ld>pairld; typedef pair<string,ll>pairsl; #define fr first #define sc second #define pb push_back #define endl '\n' #define N 100007 #define MOD 1000000007 #define INF 100000000000007 #define eps 0.00000000001 //#define A 30011 #define PI 3.14159265359 ll n,q,sz[N],pard,h,par[N],num[N],nh[N],res,u[N],o; struct HLD{ ll sz,p; }hld[N]; vector<ll>v[N],t[N],push[N]; void dfs1(ll x,ll y){ //cout<<x<<" "<<y<<endl; sz[x]=1; for(int i=0;i<v[x].size();i++){ if(v[x][i]!=y){ dfs1(v[x][i],x); sz[x]+=sz[v[x][i]]; u[x]=(u[x]+u[v[x][i]])%2; } } par[x]=y; if(v[x].size()==1){ u[x]=1; o++; } res+=u[x]; return ; } void S(ll x,ll y,ll z){ hld[z].sz++; nh[x]=z; if(nh[x]!=nh[y]){ num[x]=1; }else num[x]=num[y]+1; ll mx=0; for(int i=0;i<v[x].size();i++){ if(v[x][i]!=y){ mx=max(mx,sz[v[x][i]]); } } for(int i=0;i<v[x].size();i++){ if(v[x][i]!=y){ if(mx==sz[v[x][i]]){ S(v[x][i],x,z); }else{ h++; hld[h].p=v[x][i]; S(v[x][i],x,h); } } } return ; } void Push(ll x,ll y,ll l,ll r){ if(l==r){ t[y][x]^=1; }else{ push[y][x]^=1; t[y][x]=(r-l+1)-t[y][x]; } return ; } void Add(ll x,ll y,ll l,ll r,ll tl,ll tr){ if(r<tl || tr<l)return ; if(tl<=l && r<=tr){ if(l==r){ t[y][x]^=1; }else{ push[y][x]^=1; t[y][x]=(r-l+1)-t[y][x]; } return ; } ll m1=(l+r)/2; if(push[y][x]!=0){ push[y][x]=0; Push(x*2+1,y,l,m1); Push(x*2+2,y,m1+1,r); } Add(x*2+1,y,l,m1,tl,tr); Add(x*2+2,y,m1+1,r,tl,tr); t[y][x]=t[y][x*2+1]+t[y][x*2+2]; return ; } void A(ll x){ if(x==0)return ; //cout<<x<<" "<<hld[nh[x]].p<<endl; res-=t[nh[x]][0]; Add(0,nh[x],1,hld[nh[x]].sz,1,num[x]); res+=t[nh[x]][0]; A(par[hld[nh[x]].p]); return ; } int main(){ cin>>n>>q; for(int i=1;i<n;i++){ ll x,y; cin>>x>>y; v[x].pb(y); v[y].pb(x); } for(int i=1;i<=n;i++){ if(v[i].size()>1)pard=i; } // cout<<pard<<endl; dfs1(pard,0); //cout<<1<<endl; h++; hld[h].p=pard; S(pard,0,h); for(int i=1;i<=h;i++){ t[i].resize(4*hld[i].sz); push[i].resize(4*hld[i].sz); } for(int i=1;i<=n;i++){ if(u[i]==1)Add(0,nh[i],1,hld[nh[i]].sz,num[i],num[i]); //cout<<i<<" "<<u[i]<<" "<<nh[i]<<" "<<num[i]<<endl; } for(int i=1;i<=q;i++){ ll x; cin>>x; vector<ll>y; y.clear(); for(int j=1;j<=x;j++){ ll z; cin>>z; y.pb(z); } for(int j=0;j<x;j++){ if(sz[y[j]]==1){ o--; }else A(y[j]); sz[y[j]]++; } //cout<<res<<endl; if((o+x)%2==0)cout<<n*2-2-res+x<<endl; else cout<<-1<<endl; for(int j=0;j<x;j++){ sz[y[j]]--; if(sz[y[j]]==1){ o++; }else A(y[j]); } } return 0; }

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

cleaning.cpp: In function 'void dfs1(ll, ll)':
cleaning.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
cleaning.cpp: In function 'void S(ll, ll, ll)':
cleaning.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
cleaning.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
#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...