oj.uz

Submission #877209

# Submission time Handle Problem Language Result Execution time Memory
877209 2023-11-23T03:51:04 Z fryingduc Pastiri (COI20_pastiri) C++17
100 / 100
 533 ms 95880 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 5e5+5;
int n, k, x[maxn];
vector<int> g[maxn];
int d[maxn], h[maxn], choose[maxn], ok[maxn];

void bfs(){
    memset(d, 0x3f3f3f, sizeof(d));
    queue<int> q;
    for(int i = 1; i <= k; ++i){
        d[x[i]] = 0;
        q.push(x[i]);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v:g[u]){
            if(d[v] > d[u] + 1){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}
void pre_dfs(int u, int prev, int mx, int st){
    if(h[u] + d[u] > mx){
        mx = h[u] + d[u];
        st = u;
    }
    choose[u] = st;
    for(auto v:g[u]){
        if(v == prev) continue;
        h[v] = h[u] + 1;
        pre_dfs(v, u, mx, st);
    }
}
void dfs(int u){
    ok[u] = 1;
    for(auto v:g[u]){
        if(!ok[v] and d[v] + 1 == d[u]) dfs(v);
    }
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= k; ++i) cin >> x[i];
    bfs();
    pre_dfs(1, 0, 0, 1);
    sort(x + 1, x + k + 1, [](const int &u, const int &v) ->bool{
        return h[u] > h[v];
    });
    vector<int> res;
    for(int i = 1; i <= k; ++i){
        if(!ok[x[i]]){
            res.push_back(choose[x[i]]);
            dfs(choose[x[i]]);
        }
    }
    cout << res.size() << '\n';
    for(auto i:res) cout << i << " ";
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 86488 KB Output is correct
2 Correct 164 ms 87376 KB Output is correct
3 Correct 172 ms 87284 KB Output is correct
4 Correct 230 ms 95880 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21096 KB Output is correct
2 Correct 6 ms 21080 KB Output is correct
3 Correct 308 ms 51756 KB Output is correct
4 Correct 292 ms 55340 KB Output is correct
5 Correct 385 ms 48960 KB Output is correct
6 Correct 495 ms 52304 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 6 ms 20984 KB Output is correct
3 Correct 6 ms 21084 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 4 ms 21336 KB Output is correct
9 Correct 6 ms 20928 KB Output is correct
10 Correct 5 ms 21084 KB Output is correct
11 Correct 4 ms 20988 KB Output is correct
12 Correct 4 ms 20824 KB Output is correct
13 Correct 4 ms 21080 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 4 ms 21084 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 52560 KB Output is correct
2 Correct 404 ms 52292 KB Output is correct
3 Correct 403 ms 56544 KB Output is correct
4 Correct 363 ms 48644 KB Output is correct
5 Correct 323 ms 50880 KB Output is correct
6 Correct 381 ms 60336 KB Output is correct
7 Correct 425 ms 58916 KB Output is correct
8 Correct 451 ms 56388 KB Output is correct
9 Correct 533 ms 49252 KB Output is correct
10 Correct 384 ms 48820 KB Output is correct
11 Correct 286 ms 54592 KB Output is correct
12 Correct 315 ms 58288 KB Output is correct
13 Correct 263 ms 59128 KB Output is correct
14 Correct 251 ms 54848 KB Output is correct
15 Correct 35 ms 29988 KB Output is correct
16 Correct 456 ms 47316 KB Output is correct
17 Correct 258 ms 51436 KB Output is correct
18 Correct 362 ms 44748 KB Output is correct
19 Correct 388 ms 57940 KB Output is correct
20 Correct 421 ms 62912 KB Output is correct
21 Correct 372 ms 51464 KB Output is correct
22 Correct 353 ms 52176 KB Output is correct