제출 #1263940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263940		nguyenvietanh	Pastiri (COI20_pastiri)	C++20	100 / 100	372 ms	81968 KiB

pastiri

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){ return (l + (rng() % (r - l + 1))); }
const int N = 5e5 + 5;
const int mod = 998244353;
int n, k;
int a[N], depth[N], d[N], ans[N], check[N];
vector <int> adj[N];
bool cmp(int a, int b){
    return depth[a] > depth[b];
}
void bfs(){
    queue <int> q;
    fill (d + 1, d + n + 1, 1e9);
    for (int i = 1; i <= k; i ++){
        d[a[i]] = 0; q.push(a[i]);
    }
    while (!q.empty()){
        int u = q.front(); q.pop();
        for (auto i : adj[u]){
            if (d[i] == 1e9){
                d[i] = d[u] + 1; q.push(i);
            }
        }
    }
}
void pre_dfs(int u, int v){
    for (auto i : adj[u]){
        if (i == v) continue;
        depth[i] = depth[u] + 1;
        pre_dfs(i, u);
    }
}
void dfs(int u, int v, int res, int node){
    if (res < depth[u] + d[u]){
        res = depth[u] + d[u]; node = u;
    }
    ans[u] = node;
    for (auto i : adj[u]){
        if (i == v) continue;
        dfs(i, u, res, node);
    }
}
void update(int u){
    check[u] = 1;
    for (auto i : adj[u]){
        if (check[i] || d[i] + 1 != d[u]) continue;
        update(i);
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i ++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= k; i ++){
        cin >> a[i];
    }
    bfs();
    pre_dfs(1, 0);
    dfs(1, 0, 0, 1);
    sort(a + 1, a + k + 1, cmp);
    vector <int> trace;
    for (int i = 1; i <= k; i ++){
        if (check[a[i]]) continue;
        trace.push_back(ans[a[i]]);
        update(ans[a[i]]);
    }
    cout << trace.size() << '\n';
    for (auto i : trace) cout << i << " ";
}

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51