oj.uz

Submission #577185

# Submission time Handle Problem Language Result Execution time Memory
577185 2022-06-14T08:43:47 Z myrcella Pastiri (COI20_pastiri) C++17
100 / 100
 737 ms 79184 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 5e5+10;

int n,m;
int dis[maxn];
bool vis[maxn];
int dep[maxn];
vector <int> sheep;
queue <int> q;
vector <int> edge[maxn];
vector <int> ans;
int a[maxn];

void bfs() {
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int v:edge[u]) if (dis[v]>dis[u]+1) {
			dis[v] = dis[u] + 1;
			q.push(v);
		}
	}
	return;
}

void dfs(int u,int fa) {
	dep[u] = dep[fa]+1;
	for (int v:edge[u]) {
		if (v==fa) continue;
		dfs(v,u);
	}
}

void dfs1(int u,int fa,int mx,int opt) {
	if (dep[u]+dis[u]>mx) {
		mx = dep[u]+dis[u];
		opt = u;
	}
	a[u] = opt;
	for (int v:edge[u]) {
		if (v==fa) continue;
		dfs1(v,u,mx,opt);
	}
}

void cover(int u) {
	vis[u] = true;
	for (int v:edge[u]) {
		if (vis[v] or dis[v]+1!=dis[u]) continue;
		cover(v);
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	rep(i,1,n) {
		int u,v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	rep(i,0,m) {
		int x;
		cin>>x;
		sheep.pb(x);
		q.push(x);
		dis[x] = 0;
	}
	bfs();
	dfs(1,0);
	sort(ALL(sheep),[](const int lhs,const int rhs) {return dep[lhs]>dep[rhs];});
	dfs1(1,0,0,0);
	for (int it:sheep) {
		if (vis[it]) continue;
		cover(a[it]);
		ans.pb(a[it]);
	}
	cout<<SZ(ans)<<"\n";
	for (int it:ans) cout<<it<<" ";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 71524 KB Output is correct
2 Correct 198 ms 71912 KB Output is correct
3 Correct 219 ms 71912 KB Output is correct
4 Correct 268 ms 79184 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 10 ms 14268 KB Output is correct
3 Correct 458 ms 41040 KB Output is correct
4 Correct 503 ms 43380 KB Output is correct
5 Correct 618 ms 40672 KB Output is correct
6 Correct 737 ms 43592 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14144 KB Output is correct
2 Correct 8 ms 14036 KB Output is correct
3 Correct 8 ms 14164 KB Output is correct
4 Correct 8 ms 14036 KB Output is correct
5 Correct 8 ms 14140 KB Output is correct
6 Correct 9 ms 14144 KB Output is correct
7 Correct 8 ms 14108 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 8 ms 14092 KB Output is correct
10 Correct 8 ms 14036 KB Output is correct
11 Correct 8 ms 14036 KB Output is correct
12 Correct 8 ms 14004 KB Output is correct
13 Correct 10 ms 14064 KB Output is correct
14 Correct 9 ms 14164 KB Output is correct
15 Correct 8 ms 14164 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 41760 KB Output is correct
2 Correct 581 ms 41580 KB Output is correct
3 Correct 643 ms 45164 KB Output is correct
4 Correct 620 ms 40792 KB Output is correct
5 Correct 516 ms 39752 KB Output is correct
6 Correct 617 ms 49784 KB Output is correct
7 Correct 661 ms 47828 KB Output is correct
8 Correct 670 ms 47208 KB Output is correct
9 Correct 732 ms 40744 KB Output is correct
10 Correct 574 ms 40668 KB Output is correct
11 Correct 449 ms 42696 KB Output is correct
12 Correct 397 ms 46692 KB Output is correct
13 Correct 451 ms 48584 KB Output is correct
14 Correct 353 ms 44328 KB Output is correct
15 Correct 72 ms 18636 KB Output is correct
16 Correct 656 ms 39008 KB Output is correct
17 Correct 435 ms 40200 KB Output is correct
18 Correct 573 ms 35940 KB Output is correct
19 Correct 627 ms 46628 KB Output is correct
20 Correct 674 ms 50144 KB Output is correct
21 Correct 535 ms 40892 KB Output is correct
22 Correct 582 ms 41480 KB Output is correct