oj.uz

Submission #968632

# Submission time Handle Problem Language Result Execution time Memory
968632 2024-04-23T18:47:11 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
23 / 100
 1000 ms 174900 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[500005][25],sz[500005],cp[25][500005],ds[25][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[x][0]=fa;
	for(int i=1;i<25;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){
	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<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 lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	for(int i=19;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)];}

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[ver][0]!=ver&&dist(a[i],f[ver][0])==d[f[ver][0]]) ver=f[ver][0];
		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 351 ms 173376 KB Output is correct
2 Correct 629 ms 174000 KB Output is correct
3 Correct 662 ms 174084 KB Output is correct
4 Execution timed out 1040 ms 174900 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 33628 KB Output is correct
2 Correct 7 ms 33624 KB Output is correct
3 Correct 864 ms 120700 KB Output is correct
4 Correct 713 ms 114544 KB Output is correct
5 Execution timed out 1048 ms 142164 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31320 KB Output is correct
2 Correct 8 ms 31328 KB Output is correct
3 Correct 46 ms 31396 KB Output is correct
4 Correct 55 ms 20828 KB Output is correct
5 Correct 27 ms 33480 KB Output is correct
6 Correct 43 ms 29276 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33272 KB Output is correct
9 Correct 5 ms 23384 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 14 ms 20828 KB Output is correct
12 Correct 6 ms 20828 KB Output is correct
13 Correct 68 ms 18780 KB Output is correct
14 Correct 21 ms 33372 KB Output is correct
15 Correct 30 ms 33372 KB Output is correct

Subtask #4
0 / 51.0

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