oj.uz

Submission #652605

# Submission time Handle Problem Language Result Execution time Memory
652605 2022-10-23T13:32:24 Z kym Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 213992 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][20];
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(i,1,19) {
		if(twok[x][i-1] == -1)continue;
		twok[x][i] = twok[twok[x][i-1]][i-1];
	}
	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;
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;
		sheeps.pb(x);
	}
	dfs(1,-1);
	for(auto i:sheeps) {
		s.insert(pi(depth[i],i));
	}
	for(auto i:sheeps) {
		level[depth[i]].insert(st[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 it=s.begin(); it!=s.end(); it=s.begin()) {
		int sh=it->s;
		int dd=it->f;
		int node=it->s;
		while(node != 1 && (dist[twok[node][0]] == depth[sh] - depth[twok[node][0]]))node=twok[node][0];

		int x=sh;
		out.pb(node);
		db(node);
		for(;;) {
			
			for(auto i=level[depth[x]].lower_bound(st[node]); i!=level[depth[x]].end() && *i <= en[node];i=level[depth[x]].lower_bound(st[node])) {
				int cur=*i;
				
				s.erase(pi(depth[rev[cur]], rev[cur]));
				
				level[depth[x]].erase(i);
				
			}
			if(x==node)break;
			x=twok[x][0];
			
		}
		FOR(di,1,dist[node]) {
			if(x==1)break;
			x=twok[x][0];
			int nd=depth[x] + dist[node] - di;
			
			for(auto i=level[nd].lower_bound(st[x]); i!=level[nd].end() && *i <= en[x];i=level[nd].lower_bound(st[x])) {
				
				
				if(i==level[nd].end())break;
				int cur=*i;
				
				db2(depth[rev[cur]], rev[cur]);
				s.erase(pi(depth[rev[cur]], rev[cur]));
				level[nd].erase(i);
			}
			
		}
	}
	cout << out.size() << '\n';
	for(auto i:out)cout << i << ' ' ;
}

Compilation message

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:110:7: warning: unused variable 'dd' [-Wunused-variable]
  110 |   int dd=it->f;
      |       ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 172464 KB Output is correct
2 Correct 312 ms 172624 KB Output is correct
3 Correct 313 ms 172748 KB Output is correct
4 Correct 776 ms 213992 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 40532 KB Output is correct
2 Correct 23 ms 40568 KB Output is correct
3 Correct 587 ms 152784 KB Output is correct
4 Correct 564 ms 157524 KB Output is correct
5 Correct 761 ms 149040 KB Output is correct
6 Correct 830 ms 151168 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39892 KB Output is correct
2 Correct 22 ms 39928 KB Output is correct
3 Correct 23 ms 39968 KB Output is correct
4 Correct 21 ms 39964 KB Output is correct
5 Correct 22 ms 40088 KB Output is correct
6 Correct 20 ms 39964 KB Output is correct
7 Correct 21 ms 39892 KB Output is correct
8 Correct 22 ms 39844 KB Output is correct
9 Correct 22 ms 39884 KB Output is correct
10 Correct 20 ms 39948 KB Output is correct
11 Correct 20 ms 39764 KB Output is correct
12 Correct 21 ms 39852 KB Output is correct
13 Correct 21 ms 40020 KB Output is correct
14 Correct 20 ms 40060 KB Output is correct
15 Correct 20 ms 39984 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 153736 KB Output is correct
2 Correct 697 ms 153648 KB Output is correct
3 Execution timed out 1093 ms 178876 KB Time limit exceeded
4 Halted 0 ms 0 KB -