oj.uz

Submission #394530

# Submission time Handle Problem Language Result Execution time Memory
394530 2021-04-26T19:18:51 Z couplefire Pastiri (COI20_pastiri) C++17
100 / 100
 961 ms 150640 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005

int n, k;
vector<int> adj[MAXN];
vector<int> newadj[MAXN];
int dist[MAXN], good[MAXN], depth[MAXN];
bool sheep[MAXN], visited[MAXN];
vector<int> curstack[2*MAXN];
set<array<int, 2>, greater<array<int, 2>>> active;
vector<int> ans;

void bfs(){
    memset(dist, 63, sizeof dist);
    queue<int> q;
    for(int i = 0; i<n; i++) if(sheep[i]) q.push(i), dist[i] = 0;
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(auto u : adj[v]) if(dist[u] > dist[v]+1) dist[u] = dist[v]+1, q.push(u);
    }
}

void dfs(int v, int p, int d){
    depth[v] = d;
    curstack[depth[v]+dist[v]].push_back(v);
    if(sheep[v]) good[v] = curstack[depth[v]+dist[v]].front();
    for(auto u : adj[v]){
        if(u == p) continue;
        dfs(u, v, d+1);
    }
    curstack[depth[v]+dist[v]].pop_back();
}

void deactive(int v){
    visited[v] = 1;
    if(sheep[v]) active.erase({depth[v], v});
    for(auto u : newadj[v]){
        if(visited[u]) continue;
        deactive(u);
    }
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i<n-1; i++){
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 0; i<k; i++){
        int a; cin >> a; --a;
        sheep[a] = 1;
    }
    bfs();
    dfs(0, 0, 0);
    for(int v = 0; v<n; v++){
        for(auto u : adj[v]) if(dist[u] == dist[v]-1) newadj[v].push_back(u);
    }
    for(int v = 0; v<n; v++){
        if(sheep[v]) active.insert({depth[v], v});
    }
    while(!active.empty()){
        int v = (*active.begin())[1];
        ans.push_back(good[v]);
        deactive(good[v]);
    }
    cout << ans.size() << endl;
    for(auto x : ans) cout << x+1 << " ";
    cout << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 141372 KB Output is correct
2 Correct 304 ms 139972 KB Output is correct
3 Correct 305 ms 139972 KB Output is correct
4 Correct 447 ms 150640 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49600 KB Output is correct
2 Correct 31 ms 49596 KB Output is correct
3 Correct 627 ms 89512 KB Output is correct
4 Correct 616 ms 91468 KB Output is correct
5 Correct 728 ms 89776 KB Output is correct
6 Correct 892 ms 94148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49484 KB Output is correct
2 Correct 29 ms 49304 KB Output is correct
3 Correct 29 ms 49384 KB Output is correct
4 Correct 29 ms 49360 KB Output is correct
5 Correct 29 ms 49432 KB Output is correct
6 Correct 29 ms 49348 KB Output is correct
7 Correct 28 ms 49336 KB Output is correct
8 Correct 28 ms 49356 KB Output is correct
9 Correct 28 ms 49360 KB Output is correct
10 Correct 28 ms 49364 KB Output is correct
11 Correct 29 ms 49292 KB Output is correct
12 Correct 28 ms 49276 KB Output is correct
13 Correct 29 ms 49412 KB Output is correct
14 Correct 29 ms 49400 KB Output is correct
15 Correct 29 ms 49476 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 93512 KB Output is correct
2 Correct 720 ms 93500 KB Output is correct
3 Correct 889 ms 97896 KB Output is correct
4 Correct 753 ms 92096 KB Output is correct
5 Correct 671 ms 89920 KB Output is correct
6 Correct 961 ms 106228 KB Output is correct
7 Correct 948 ms 102136 KB Output is correct
8 Correct 912 ms 101264 KB Output is correct
9 Correct 860 ms 94156 KB Output is correct
10 Correct 731 ms 90116 KB Output is correct
11 Correct 573 ms 93608 KB Output is correct
12 Correct 698 ms 100452 KB Output is correct
13 Correct 835 ms 103680 KB Output is correct
14 Correct 528 ms 94764 KB Output is correct
15 Correct 106 ms 56644 KB Output is correct
16 Correct 791 ms 89136 KB Output is correct
17 Correct 638 ms 89880 KB Output is correct
18 Correct 696 ms 84276 KB Output is correct
19 Correct 832 ms 100944 KB Output is correct
20 Correct 788 ms 106724 KB Output is correct
21 Correct 704 ms 91972 KB Output is correct
22 Correct 752 ms 93180 KB Output is correct