Submission #968623

#	Time	Username	Problem	Language	Result	Execution time	Memory
968623		MilosMilutinovic	Pastiri (COI20_pastiri)	C++14	31 / 100	1049 ms	201312 KiB

pastiri

#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);
	}
}

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){
	assert(dd<25);
	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:138:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  138 |  printf("%d\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51