oj.uz

Submission #968642

# Submission time Handle Problem Language Result Execution time Memory
968642 2024-04-23T19:05:29 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
23 / 100
 1000 ms 96744 KB 
#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[21][500005],sz[500005],cp[21][500005],ds[21][500005],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[0][x]=fa;
	for(int i=1;i<21;i++) f[i][x]=f[i-1][f[i-1][x]];
	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){
	//cp[dd][x]=s;
	//ds[dd][x]=ds[dd][fa]+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<21;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<21;i++){
		chkmax(mx[cp[x][i]],d[x]+1-(ds[x][i]-1));
		if(cp[x][i]==x) break;
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x];
	for(int i=10;i>=0;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
	return x==y?x:f[0][x];
}
 
int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}

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++){
		bool ok=false;
		for(int j=1;j<=n;j++){
			if(hv[j]&&dist(a[i],j)==d[j]) ok=true;
		}
		if(ok) continue;
		int ver=a[i];
		while(f[0][ver]!=ver&&dep[a[i]]-dep[f[0][ver]]==d[f[0][ver]]) ver=f[0][ver];
		hv[ver]=true;	
	}
	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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 95024 KB Output is correct
2 Correct 637 ms 95768 KB Output is correct
3 Correct 653 ms 95500 KB Output is correct
4 Execution timed out 1085 ms 96744 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51804 KB Output is correct
2 Correct 9 ms 51804 KB Output is correct
3 Correct 532 ms 60356 KB Output is correct
4 Correct 473 ms 60328 KB Output is correct
5 Execution timed out 1046 ms 59852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 51548 KB Output is correct
2 Correct 9 ms 51548 KB Output is correct
3 Correct 36 ms 51548 KB Output is correct
4 Correct 43 ms 51796 KB Output is correct
5 Correct 23 ms 51544 KB Output is correct
6 Correct 35 ms 51780 KB Output is correct
7 Correct 7 ms 51548 KB Output is correct
8 Correct 7 ms 51776 KB Output is correct
9 Correct 7 ms 51548 KB Output is correct
10 Correct 8 ms 51544 KB Output is correct
11 Correct 17 ms 51548 KB Output is correct
12 Correct 8 ms 51548 KB Output is correct
13 Correct 47 ms 51680 KB Output is correct
14 Correct 18 ms 51800 KB Output is correct
15 Correct 26 ms 51544 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 61008 KB Time limit exceeded
2 Halted 0 ms 0 KB -