Submission #968622

#TimeUsernameProblemLanguageResultExecution timeMemory
968622MilosMilutinovicPastiri (COI20_pastiri)C++14
31 / 100
1059 ms201244 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} ll readint(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,k,tot; int v[1000005],nxt[1000005],h[500005],a[500005],dep[500005],d[500005],f[500005][25],sz[500005],cp[500005][25],ds[500005][25],mx[500005]; bool hv[500005],del[500005]; void addedge(int x,int y){ v[++tot]=y; nxt[tot]=h[x]; h[x]=tot; v[++tot]=x; nxt[tot]=h[y]; h[y]=tot; } void dfs(int x,int fa){ dep[x]=dep[fa]+1; f[x][0]=fa; for(int i=1;i<24;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int p=h[x];p;p=nxt[p]){ if(v[p]==fa) continue; dfs(v[p],x); } } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=24;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; for(int i=24;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return x==y?x:f[x][0]; } int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];} void bfs(){ for(int i=1;i<=n;i++) d[i]=-1; queue<int> q; for(int i=1;i<=k;i++){ d[a[i]]=0; q.push(a[i]); } while(!q.empty()){ int x=q.front(); q.pop(); for(int p=h[x];p;p=nxt[p]){ if(d[v[p]]==-1){ d[v[p]]=d[x]+1; q.push(v[p]); } } } } void dfssz(int x,int fa){ sz[x]=1; for(int p=h[x];p;p=nxt[p]){ if(del[v[p]]||v[p]==fa) continue; dfssz(v[p],x); sz[x]+=sz[v[p]]; } } int findcen(int x,int fa,int n){ for(int p=h[x];p;p=nxt[p]){ if(del[v[p]]||v[p]==fa||sz[v[p]]*2<n) continue; return findcen(v[p],x,n); } return x; } void go(int x,int fa,int s,int dd){ cp[x][dd]=s; ds[x][dd]=ds[fa][dd]+1; for(int p=h[x];p;p=nxt[p]){ if(del[v[p]]||v[p]==fa) continue; go(v[p],x,s,dd); } } void build(int x,int dd){ dfssz(x,x); x=findcen(x,x,sz[x]); del[x]=true; go(x,x,x,dd); for(int p=h[x];p;p=nxt[p]){ if(del[v[p]]) continue; build(v[p],dd+1); } } bool query(int x){ for(int i=0;i<25;i++){ if(mx[cp[x][i]]>=ds[x][i]) return true; if(cp[x][i]==x) break; } return false; } void update(int x){ for(int i=0;i<25;i++){ chkmax(mx[cp[x][i]],d[x]+1-(ds[x][i]-1)); if(cp[x][i]==x) break; } } int main(){ n=readint(); k=readint(); for(int i=1;i<n;i++) addedge(readint(),readint()); for(int i=1;i<=k;i++) a[i]=readint(); dfs(1,1); bfs(); build(1,0); sort(a+1,a+k+1,[&](int i,int j){return dep[i]>dep[j];}); for(int i=1;i<=k;i++){ if(query(a[i])) continue; int ver=a[i]; for(int j=24;j>=0;j--){ if(d[f[ver][j]]==dep[a[i]]-dep[f[ver][j]]){ ver=f[ver][j]; } } hv[ver]=true; update(ver); } vector<int> ans; for(int i=1;i<=n;i++) if(hv[i]) ans.pb(i); printf("%d\n",ans.size()); for(int i:ans) printf("%d ",i); return 0; }

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:146:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  146 |  printf("%d\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...