oj.uz

답안 #968631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968631 2024-04-23T18:45:09 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
41 / 100
 1000 ms 98628 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 246 ms 97368 KB Output is correct
2 Correct 537 ms 97748 KB Output is correct
3 Correct 566 ms 97792 KB Output is correct
4 Execution timed out 1066 ms 98628 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 403 ms 66436 KB Output is correct
4 Correct 400 ms 66488 KB Output is correct
5 Correct 776 ms 66204 KB Output is correct
6 Correct 836 ms 69164 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 44 ms 12636 KB Output is correct
4 Correct 54 ms 12636 KB Output is correct
5 Correct 25 ms 12636 KB Output is correct
6 Correct 42 ms 12636 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 4 ms 12804 KB Output is correct
10 Correct 4 ms 12636 KB Output is correct
11 Correct 14 ms 12636 KB Output is correct
12 Correct 5 ms 12636 KB Output is correct
13 Correct 67 ms 12776 KB Output is correct
14 Correct 19 ms 12636 KB Output is correct
15 Correct 27 ms 12632 KB Output is correct

Subtask #4
0 / 51.0

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