oj.uz

답안 #968630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968630 2024-04-23T18:44:29 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
41 / 100
 1000 ms 91168 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[500005][25],ds[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]);
			}
		}
	}
}

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[x][dd]=s;
	ds[x][dd]=ds[fa][dd]+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

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 88916 KB Output is correct
2 Correct 411 ms 89364 KB Output is correct
3 Correct 451 ms 89580 KB Output is correct
4 Execution timed out 1062 ms 91168 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 274 ms 66068 KB Output is correct
4 Correct 246 ms 66068 KB Output is correct
5 Correct 318 ms 65616 KB Output is correct
6 Correct 529 ms 71264 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 44 ms 12796 KB Output is correct
4 Correct 56 ms 12772 KB Output is correct
5 Correct 24 ms 12632 KB Output is correct
6 Correct 41 ms 12776 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 4 ms 12760 KB Output is correct
11 Correct 13 ms 12800 KB Output is correct
12 Correct 5 ms 12636 KB Output is correct
13 Correct 67 ms 12636 KB Output is correct
14 Correct 18 ms 12632 KB Output is correct
15 Correct 26 ms 12636 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1022 ms 66492 KB Time limit exceeded
2 Halted 0 ms 0 KB -