oj.uz

Submission #1003915

# Submission time Handle Problem Language Result Execution time Memory
1003915 2024-06-20T19:54:57 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 485 ms 83488 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 5e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

struct segTree{
	vector<int> tree;
	int N;
	
	void init(int n){
		N=n;
		tree.resize(4*N, INF);
	}
	
	void update(int node, int l, int r, int p, int val){
		if(r<p || l>p) return;
		if(l==r){
			tree[node]=val;
			return;
		}
		
		int mid=(l+r)>>1;
		
		update(node*2, l, mid, p, val);
		update(node*2+1, mid+1, r, p, val);
		
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	
	int query(int node, int l, int r, int p, int q){
		if(r<p || l>q) return INF;
		if(l>=p && r<=q) return tree[node];
		int mid=(l+r)>>1;
		return min(query(node*2, l, mid, p, q), query(node*2+1, mid+1, r, p, q));
	}
	
	void upd(int p, int val){ update(1, 1, N, p, val); }
	int getMin(int l, int r){ return query(1, 1, N, l, r); }
};
		

vector<int> adj[MAXN];
int prof[MAXN], dist[MAXN], elim[MAXN], pai[MAXN], tin[MAXN], tout[MAXN];

void build(int ver, int& t, int prev=0){
	prof[ver]=prof[prev]+1;
	pai[ver]=prev;
	tin[ver]=t;
	
	for(auto u : adj[ver]){
		if(u==prev) continue;
		t++;
		build(u, t, ver);
	}
	
	tout[ver]=t;
}

void dfs(int ver, int val, int lim){
	elim[ver]=1;
	if(val==lim) return;
	
	for(auto u : adj[ver]){
		if(u==pai[ver] || elim[u]) continue;
		dfs(u, val+1, lim);
	}
}

void solve(){
	int n, k; cin >> n >> k;
	
	for(int i=0;i<n-1;i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	
	for(int i=1;i<=n;i++)
		dist[i]=-1;
	
	vector<int> spec(k);
	queue<int> q;
	for(int i=0;i<k;i++){
		cin >> spec[i];
		q.push(spec[i]);
		dist[spec[i]]=0;
	}
	
	while(!q.empty()){
		int curr=q.front();
		q.pop();
		
		for(auto u : adj[curr]){
			if(dist[u]==-1){
				dist[u]=dist[curr]+1;
				q.push(u);
			}
		}
	}
	
	int temp=1;
	build(1, temp);
	sort(all(spec), [&](int a, int b){ return prof[a]>prof[b]; });
	
	segTree arvore;
	arvore.init(n);
	
	vector<int> ans;
	for(auto u : spec){
		if(elim[u]) continue;
		
		int at=u, d=0, aux;
		bool ok=1;
		while(pai[at]!=0 && dist[pai[at]]==d+1){
			aux=arvore.getMin(tin[at], tout[at]);
			if(prof[at]-aux>=d){
				ok=0;
				dfs(at, 0, prof[at]-aux);
				break;
			}
			d++;
			at=pai[at];
		}
		
		if(!ok) continue;
		
		aux=arvore.getMin(tin[at], tout[at]);
		if(prof[at]-aux>=d){
			dfs(at, 0, prof[at]-aux);
			continue;
		}
		
		ans.pb(at);
		arvore.upd(tin[at], prof[at]-d);
		dfs(at, 0, d);
	}
	
	cout << (int)ans.size() << "\n";
	for(int i=0;i<(int)ans.size();i++) cout << ans[i] << " \n"[i==(int)ans.size()-1];
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 78672 KB Output is correct
2 Correct 115 ms 78600 KB Output is correct
3 Correct 129 ms 78504 KB Output is correct
4 Correct 204 ms 83488 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19804 KB Output is correct
2 Correct 4 ms 19880 KB Output is correct
3 Correct 200 ms 54376 KB Output is correct
4 Correct 214 ms 56912 KB Output is correct
5 Correct 303 ms 54100 KB Output is correct
6 Correct 485 ms 56700 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19548 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct
6 Correct 4 ms 19804 KB Output is correct
7 Correct 3 ms 19804 KB Output is correct
8 Correct 4 ms 19804 KB Output is correct
9 Correct 4 ms 19832 KB Output is correct
10 Correct 3 ms 19800 KB Output is correct
11 Correct 3 ms 19544 KB Output is correct
12 Correct 3 ms 19548 KB Output is correct
13 Correct 4 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct
15 Correct 4 ms 19804 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 48208 KB Output is correct
2 Correct 357 ms 54828 KB Output is correct
3 Correct 396 ms 58608 KB Output is correct
4 Correct 312 ms 53840 KB Output is correct
5 Correct 306 ms 52332 KB Output is correct
6 Correct 303 ms 62732 KB Output is correct
7 Correct 353 ms 61012 KB Output is correct
8 Correct 386 ms 60368 KB Output is correct
9 Correct 413 ms 54040 KB Output is correct
10 Correct 269 ms 54112 KB Output is correct
11 Correct 170 ms 55892 KB Output is correct
12 Correct 159 ms 59720 KB Output is correct
13 Correct 185 ms 61848 KB Output is correct
14 Correct 146 ms 57460 KB Output is correct
15 Correct 23 ms 25432 KB Output is correct
16 Correct 279 ms 51796 KB Output is correct
17 Correct 263 ms 52676 KB Output is correct
18 Correct 210 ms 48464 KB Output is correct
19 Correct 260 ms 59988 KB Output is correct
20 Correct 304 ms 63568 KB Output is correct
21 Correct 204 ms 54148 KB Output is correct
22 Correct 192 ms 54612 KB Output is correct