oj.uz

답안 #968650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968650 2024-04-23T19:34:29 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 99216 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],lst[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;
	lst[x]=x;
	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(lst[v[p]]!=x){
				q.push(mp(v[p],val.se+1));
				del[v[p]]=true;
				lst[v[p]]=x;
			}
		}
	}
}
 
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:113:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  113 |  printf("%d\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 95056 KB Output is correct
2 Correct 124 ms 94776 KB Output is correct
3 Correct 128 ms 94968 KB Output is correct
4 Correct 227 ms 99216 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 257 ms 71904 KB Output is correct
4 Correct 257 ms 72568 KB Output is correct
5 Correct 333 ms 71276 KB Output is correct
6 Correct 658 ms 75348 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 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 12632 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 4 ms 12632 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 7 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 3 ms 12636 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 72732 KB Output is correct
2 Correct 301 ms 75504 KB Output is correct
3 Correct 372 ms 77252 KB Output is correct
4 Correct 291 ms 74312 KB Output is correct
5 Correct 258 ms 66384 KB Output is correct
6 Correct 403 ms 79076 KB Output is correct
7 Correct 470 ms 78876 KB Output is correct
8 Correct 466 ms 78688 KB Output is correct
9 Execution timed out 1047 ms 74444 KB Time limit exceeded
10 Halted 0 ms 0 KB -