oj.uz

답안 #968655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968655 2024-04-23T19:40:40 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
49 / 100
 430 ms 94292 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],mn[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;
	mn[x]=0;
	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(mn[v[p]]>val.se+1){
				q.push(mp(v[p],val.se+1));
				del[v[p]]=true;
				mn[v[p]]=val.se+1;
			}
		}
	}
}
 
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<=n;i++) mn[i]=1000000000;
	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:114:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  114 |  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 114 ms 91232 KB Output is correct
2 Correct 127 ms 91216 KB Output is correct
3 Correct 136 ms 91288 KB Output is correct
4 Correct 239 ms 94292 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 259 ms 68256 KB Output is correct
4 Correct 300 ms 68348 KB Output is correct
5 Correct 365 ms 67728 KB Output is correct
6 Correct 430 ms 69716 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 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 2 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 12632 KB Output is correct
11 Correct 2 ms 12768 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
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 304 ms 68280 KB Output isn't correct
2 Halted 0 ms 0 KB -