oj.uz

Submission #652709

# Submission time Handle Problem Language Result Execution time Memory
652709 2022-10-24T02:21:59 Z kym Pastiri (COI20_pastiri) C++14
100 / 100
 819 ms 130984 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 	
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 500005;
int n,k;
vector<int> V[MAXN];
vector<int> sheeps;
set<int> level[MAXN];
int depth[MAXN];
int twok[MAXN][1];
int st[MAXN], en[MAXN];
int cnt=1;
int rev[MAXN];

void dfs(int x, int p) {
	st[x]=cnt;
	rev[cnt]=x;
	++cnt;
	twok[x][0]=p;
	for(auto v:V[x])if(v!=p) {
		depth[v]=depth[x]+1;
		dfs(v,x);
	}
	en[x]=cnt-1;
}
int dist[MAXN];
set<pi,greater<pi>> s;
vector<int>out;
bool vis[MAXN];
bool is[MAXN];
void clearr(int x) {
	
	if(vis[x])return;
	vis[x]=1;
	for(auto v:V[x]){
		if(vis[v])continue;
		if(dist[x]==dist[v]+1)clearr(v);
	}
}

int32_t main() 
{
	IAMSPEED
	cin >> n >> k;
	FOR(i,1,n-1) {
		int a,b; cin >> a >> b;
		V[a].pb(b);
		V[b].pb(a);
	}
	FOR(i,1,k) {
		int x; cin >> x;
		is[x]=1;
		sheeps.pb(x);
	}
	dfs(1,-1);
	for(auto i:sheeps) {
		s.insert(pi(depth[i],i));
	}
	queue<int> q;
	FOR(i,0,MAXN-1)dist[i]=oo;
	for(auto i:sheeps){
		q.push(i);
		dist[i]=0;
	}
	while(q.size()) {
		int x=q.front(); 
		q.pop();
		for(auto v:V[x]){
			if(dist[v] > dist[x]+1) {
				dist[v]=dist[x]+1;
				q.push(v);
			}
		}
	}
	for(auto sheep:s){
		int x=sheep.s; int dd=sheep.f;
		if(vis[x])continue;
		int node=x;
		while(node != 1 && (dist[twok[node][0]] == depth[x] - depth[twok[node][0]]))node=twok[node][0];
		out.pb(node);
		clearr(node);
	}
	cout << out.size() << '\n';
	for(auto i:out)cout << i << ' ' ;
}

Compilation message

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:116:22: warning: unused variable 'dd' [-Wunused-variable]
  116 |   int x=sheep.s; int dd=sheep.f;
      |                      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 103180 KB Output is correct
2 Correct 216 ms 104112 KB Output is correct
3 Correct 231 ms 103832 KB Output is correct
4 Correct 499 ms 130984 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39864 KB Output is correct
2 Correct 22 ms 39880 KB Output is correct
3 Correct 474 ms 83644 KB Output is correct
4 Correct 441 ms 88272 KB Output is correct
5 Correct 581 ms 80208 KB Output is correct
6 Correct 752 ms 82316 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39636 KB Output is correct
2 Correct 19 ms 39680 KB Output is correct
3 Correct 21 ms 39772 KB Output is correct
4 Correct 20 ms 39632 KB Output is correct
5 Correct 21 ms 39784 KB Output is correct
6 Correct 23 ms 39768 KB Output is correct
7 Correct 22 ms 39676 KB Output is correct
8 Correct 19 ms 39608 KB Output is correct
9 Correct 21 ms 39616 KB Output is correct
10 Correct 19 ms 39636 KB Output is correct
11 Correct 19 ms 39636 KB Output is correct
12 Correct 21 ms 39664 KB Output is correct
13 Correct 20 ms 39636 KB Output is correct
14 Correct 24 ms 39724 KB Output is correct
15 Correct 27 ms 39652 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 84512 KB Output is correct
2 Correct 547 ms 84404 KB Output is correct
3 Correct 715 ms 100592 KB Output is correct
4 Correct 581 ms 82400 KB Output is correct
5 Correct 538 ms 93244 KB Output is correct
6 Correct 819 ms 114256 KB Output is correct
7 Correct 772 ms 106936 KB Output is correct
8 Correct 741 ms 103740 KB Output is correct
9 Correct 717 ms 82424 KB Output is correct
10 Correct 574 ms 81952 KB Output is correct
11 Correct 419 ms 89072 KB Output is correct
12 Correct 588 ms 105304 KB Output is correct
13 Correct 665 ms 114752 KB Output is correct
14 Correct 408 ms 89676 KB Output is correct
15 Correct 87 ms 48368 KB Output is correct
16 Correct 648 ms 80800 KB Output is correct
17 Correct 531 ms 93936 KB Output is correct
18 Correct 585 ms 74868 KB Output is correct
19 Correct 600 ms 95536 KB Output is correct
20 Correct 612 ms 95572 KB Output is correct
21 Correct 532 ms 85072 KB Output is correct
22 Correct 522 ms 85444 KB Output is correct