제출 #557526

#제출 시각아이디문제언어결과실행 시간메모리
557526krit3379Railway (BOI17_railway)C++17
0 / 100
117 ms42352 KiB
#include<bits/stdc++.h> using namespace std; #define N 100005 #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") int cnt[N],dep[N],head[N],heavy[N],p[N],id[N],out[N],sz; pair<int,int> t[4*N],lazy[4*N]; vector<int> v,ans; vector<pair<int,int>> g[N]; void dfs(int s,int f){ int ma=0; cnt[s]=1; dep[s]=dep[f]+1; heavy[s]=-1; p[s]=f; for(auto [x,i]:g[s]){ if(x==f)continue; out[x]=i; dfs(x,s); cnt[s]+=cnt[x]; if(cnt[x]>ma)ma=cnt[x],heavy[s]=x; } } void hld(int s,int f,int h){ head[s]=h; id[s]=++sz; if(heavy[s]!=-1)hld(heavy[s],s,h); for(auto [x,i]:g[s]){ if(x==f||x==heavy[s])continue; hld(x,s,x); } return ; } int lca(int a,int b){ while(head[a]!=head[b]){ if(dep[head[a]]>dep[head[b]])a=p[head[a]]; else b=p[head[b]]; } if(dep[a]<dep[b])return a; else return b; } void push(int x,int l,int r){ if(lazy[x].first){ if(t[x].second!=lazy[x].second)t[x].first+=lazy[x].first,t[x].second=lazy[x].second; if(l!=r){ if(lazy[x*2].second!=lazy[x].second)lazy[x*2].first+=lazy[x].first,lazy[x*2+1].second=lazy[x].second; if(lazy[x*2+1].second!=lazy[x].second)lazy[x*2+1].first+=lazy[x].first,lazy[x*2+1].second=lazy[x].second; } lazy[x]={0,0}; } } void upd(int x,int l,int r,int ll,int rr,int val){ push(x,l,r); if(l>rr||ll>r)return ; if(ll<=l&&r<=rr){ if(lazy[x].second!=val)lazy[x].first++,lazy[x].second=val; push(x,l,r); return ; } int mid=(l+r)/2; upd(x*2,l,mid,ll,rr,val); upd(x*2+1,mid+1,r,ll,rr,val); } void update(int a,int l,int val){ while(head[a]!=head[l]){ upd(1,1,sz,id[head[a]],id[a],val); a=p[head[a]]; } if(a!=l)upd(1,1,sz,id[l]+1,id[a],val); } int sol(int x,int l,int r,int p){ push(x,l,r); if(l>p||p>r)return 0; if(l==r)return t[x].first; int mid=(l+r)/2; return sol(x*2,l,mid,p)+sol(x*2+1,mid+1,r,p); } int main(){ int n,m,k,i,a,b,t,x,l; scanf("%d %d %d",&n,&m,&k); for(i=1;i<n;i++){ scanf("%d %d",&a,&b); g[a].push_back({b,i}); g[b].push_back({a,i}); } dfs(1,0); hld(1,0,1); while(m--){ scanf("%d",&t); for(i=1;i<=t;i++)scanf("%d",&x),v.push_back(x); l=v[0]; for(i=1;i<v.size();i++)l=lca(l,v[i]); for(auto x:v)update(x,l,m+1); v.clear(); } for(i=1;i<=n;i++)if(sol(1,1,n,id[i])>=k)ans.push_back(out[i]); sort(ans.begin(),ans.end()); printf("%d\n",ans.size()); for(auto x:ans)printf("%d ",x); return 0; }

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

railway.cpp: In function 'int main()':
railway.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(i=1;i<v.size();i++)l=lca(l,v[i]);
      |                 ~^~~~~~~~~
railway.cpp:107:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  107 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
railway.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d %d %d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
railway.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
railway.cpp:99:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         for(i=1;i<=t;i++)scanf("%d",&x),v.push_back(x);
      |                          ~~~~~^~~~~~~~~
#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...