oj.uz

답안 #968567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968567 2024-04-23T15:50:15 Z MilosMilutinovic Pastiri (COI20_pastiri) C++14
41 / 100
 1000 ms 88500 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][20];
bool hv[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<20;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);
	}
}

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)];}

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 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++){
		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:92:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |  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 115 ms 85328 KB Output is correct
2 Correct 417 ms 85584 KB Output is correct
3 Correct 488 ms 85644 KB Output is correct
4 Execution timed out 1040 ms 88500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10760 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 231 ms 62612 KB Output is correct
4 Correct 217 ms 62516 KB Output is correct
5 Correct 262 ms 61932 KB Output is correct
6 Correct 353 ms 64080 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 5 ms 10584 KB Output is correct
3 Correct 42 ms 10588 KB Output is correct
4 Correct 53 ms 10588 KB Output is correct
5 Correct 24 ms 10724 KB Output is correct
6 Correct 38 ms 10588 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 4 ms 10588 KB Output is correct
11 Correct 13 ms 10744 KB Output is correct
12 Correct 5 ms 10588 KB Output is correct
13 Correct 67 ms 10588 KB Output is correct
14 Correct 17 ms 10784 KB Output is correct
15 Correct 26 ms 10752 KB Output is correct

Subtask #4
0 / 51.0

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