oj.uz

Submission #968676

# Submission time Handle Problem Language Result Execution time Memory
968676 2024-04-23T20:03:01 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
100 / 100
 472 ms 93212 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],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]);
			}
		}
	}
}
 
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 update(int x){
	queue<pii> q;
	q.push(mp(x,0));
	del[x]=true;
	while(!q.empty()){
		auto val=q.front();
		q.pop();
		int t=val.fi;
		if(val.se==d[x]) continue;
		for(int p=h[t];p;p=nxt[p]){
			if(!del[v[p]]&&d[v[p]]==d[t]-1){
				q.push(mp(v[p],val.se+1));
				del[v[p]]=true;
			}
		}
	}
}
 
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();
	sort(a+1,a+k+1,[&](int i,int j){return dep[i]>dep[j];});
	for(int i=1;i<=k;i++){
		if(del[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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 91220 KB Output is correct
2 Correct 125 ms 90520 KB Output is correct
3 Correct 118 ms 89940 KB Output is correct
4 Correct 219 ms 93212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 248 ms 66200 KB Output is correct
4 Correct 240 ms 68024 KB Output is correct
5 Correct 295 ms 66160 KB Output is correct
6 Correct 426 ms 70080 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12648 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 67216 KB Output is correct
2 Correct 333 ms 68364 KB Output is correct
3 Correct 340 ms 68032 KB Output is correct
4 Correct 309 ms 66408 KB Output is correct
5 Correct 252 ms 58592 KB Output is correct
6 Correct 383 ms 70568 KB Output is correct
7 Correct 472 ms 69472 KB Output is correct
8 Correct 404 ms 69512 KB Output is correct
9 Correct 311 ms 67904 KB Output is correct
10 Correct 287 ms 72816 KB Output is correct
11 Correct 252 ms 73808 KB Output is correct
12 Correct 285 ms 75296 KB Output is correct
13 Correct 286 ms 77624 KB Output is correct
14 Correct 258 ms 75124 KB Output is correct
15 Correct 27 ms 24736 KB Output is correct
16 Correct 301 ms 70012 KB Output is correct
17 Correct 267 ms 64956 KB Output is correct
18 Correct 249 ms 63572 KB Output is correct
19 Correct 383 ms 77500 KB Output is correct
20 Correct 450 ms 80464 KB Output is correct
21 Correct 261 ms 72596 KB Output is correct
22 Correct 287 ms 73300 KB Output is correct