oj.uz

Submission #976386

# Submission time Handle Problem Language Result Execution time Memory
976386 2024-05-06T13:51:53 Z efedmrlr Pastiri (COI20_pastiri) C++17
100 / 100
 674 ms 95312 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,popcnt")
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define MP make_pair

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 5e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;
vector<vector<int> > adj(N, vector<int>()), g(N, vector<int>());
vector<int> she;
vector<int> dist(N, -1), dep(N, 0);
vector<int> p(N, 0);
vector<int> vis(N, 0), a(N, 0);
void bfs() {
    queue<int> qu;
    for(auto c : she) {
        dist[c] = 0;
        qu.push(c);
    }
    while(qu.size()) {
        auto cur = qu.front();
        qu.pop();
        for(auto c : adj[cur]) {
            if(dist[c] != -1) continue;
            dist[c] = dist[cur] + 1;
            qu.push(c); 
        }
    }
} 

void dfs(int node, int par) {
    for(auto c : adj[node]) {
        if(c == par) continue;
        dep[c] = dep[node] + 1;
        p[c] = node;
        dfs(c, node);
    }
}
void dfs2(int node) {
    vis[node] = 1;
    for(auto c : g[node]) {
        if(vis[c]) continue;
        dfs2(c);
    }
}
void solve() {
    int n, k;
    cin >> n >> k;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    she.resize(k);
    REP(i, k) {
        cin >> she[i];
    }
    dfs(1, 0);
    bfs();
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dep:" << dep[i] << " dist:" << dist[i] << "\n";
    // }
    for(auto c : she) {
        int last = c;
        while(last != 1 && dist[last] < dist[p[last]]) {
            last = p[last];
        }
        a[c] = last;
        // cout << "c:" << c << " ac:" << a[c] << "\n";
    }
    for(int i = 1; i <= n; i++) {
        for(int c : adj[i]) {
            if(dist[c] == dist[i] + 1) {
                g[c].pb(i);
            }
        }
    }
    sort(all(she), [](int x, int y) {
        return dep[x] > dep[y];
    });
    vector<int> res;
    for(auto c : she) {
        if(vis[c]) continue;
        res.pb(a[c]);
        dfs2(a[c]);
    }
    cout << res.size() << "\n";
    for(auto c : res) {
        cout << c << " ";
    }
    cout << "\n";
}

signed main() {
    fastio();
    solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 88348 KB Output is correct
2 Correct 179 ms 88504 KB Output is correct
3 Correct 186 ms 95312 KB Output is correct
4 Correct 298 ms 91556 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33884 KB Output is correct
2 Correct 18 ms 33888 KB Output is correct
3 Correct 387 ms 71696 KB Output is correct
4 Correct 430 ms 73480 KB Output is correct
5 Correct 545 ms 71684 KB Output is correct
6 Correct 674 ms 73620 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33880 KB Output is correct
2 Correct 13 ms 33884 KB Output is correct
3 Correct 13 ms 33884 KB Output is correct
4 Correct 13 ms 33752 KB Output is correct
5 Correct 15 ms 33764 KB Output is correct
6 Correct 16 ms 33884 KB Output is correct
7 Correct 13 ms 33884 KB Output is correct
8 Correct 12 ms 33880 KB Output is correct
9 Correct 14 ms 33884 KB Output is correct
10 Correct 13 ms 33724 KB Output is correct
11 Correct 13 ms 33736 KB Output is correct
12 Correct 14 ms 33624 KB Output is correct
13 Correct 15 ms 33744 KB Output is correct
14 Correct 14 ms 33828 KB Output is correct
15 Correct 13 ms 33692 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 65572 KB Output is correct
2 Correct 504 ms 72060 KB Output is correct
3 Correct 514 ms 68928 KB Output is correct
4 Correct 537 ms 71508 KB Output is correct
5 Correct 381 ms 61768 KB Output is correct
6 Correct 515 ms 70472 KB Output is correct
7 Correct 540 ms 70616 KB Output is correct
8 Correct 591 ms 71372 KB Output is correct
9 Correct 657 ms 71704 KB Output is correct
10 Correct 567 ms 71688 KB Output is correct
11 Correct 424 ms 72784 KB Output is correct
12 Correct 324 ms 71492 KB Output is correct
13 Correct 362 ms 70248 KB Output is correct
14 Correct 327 ms 74312 KB Output is correct
15 Correct 50 ms 39252 KB Output is correct
16 Correct 556 ms 68160 KB Output is correct
17 Correct 348 ms 62660 KB Output is correct
18 Correct 481 ms 64608 KB Output is correct
19 Correct 537 ms 73708 KB Output is correct
20 Correct 537 ms 77392 KB Output is correct
21 Correct 493 ms 71716 KB Output is correct
22 Correct 508 ms 72140 KB Output is correct