oj.uz

Submission #714491

# Submission time Handle Problem Language Result Execution time Memory
714491 2023-03-24T17:06:34 Z nifeshe Pastiri (COI20_pastiri) C++17
100 / 100
 822 ms 100868 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
//#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef long double ld;

const ll mod = 1e9 + 7;
const ll base = 1e6 + 9;
const ll inf = 1e9;
const int MAX = 5e5 + 15;
const int LG = 19;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int n;
int timer = 0;
int tin[MAX], tout[MAX], d[MAX];
int up[MAX][LG];
vector<int> g[MAX];

void dfs(int v, int p = 0) {
    tin[v] = timer++;
    up[v][0] = p;
    for(auto to : g[v]) {
        if(to == p) continue;
        d[to] = d[v] + 1;
        dfs(to, v);
    }
    tout[v] = timer;
}

bool anc(int u, int v) {
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int LCA(int u, int v) {
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    for(int l = LG - 1; ~l; l--) {
        if(!anc(up[u][l], v)) u = up[u][l];
    }
    return up[u][0];
}

int dist(int u, int v) {
    return d[u] + d[v] - 2 * d[LCA(u, v)];
}

void solve() {
    int k;
    cin >> n >> k;
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> a(k);
    for(auto &i : a) {
        cin >> i;
    }
    dfs(1);
    for(int l = 1; l < LG; l++) {
        for(int v = 1; v <= n; v++) {
            up[v][l] = up[up[v][l - 1]][l - 1];
        }
    }
    vector<int> dist(n + 1, inf);
    queue<int> q;
    for(auto v : a) {
        dist[v] = 0;
        q.push(v);
    }
    while(sz(q)) {
        int v = q.front(); q.pop();
        for(auto to : g[v]) {
            if(dist[to] > dist[v] + 1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }
    vector<int> ans;
    vector<pair<int, int>> order;
    vector<int> c(n + 1);
    for(auto v : a) c[v] = 1;
    for(auto v : a) order.pb({d[v], v});
    sort(rall(order));
    vector<int> used(n + 1);
    function<void(int, int)> update = [&](int v, int dst) {
        used[v] = 1;
        if(dst == 0) return;
        for(auto to : g[v]) {
            if(used[to] || (dist[to] != dist[v] - 1)) continue;
            update(to, dst - 1);
        }
    };
    for(auto [useless, v] : order) {
        if(used[v]) continue;
        int u = v;
        for(int l = LG - 1; ~l; l--) {
            if(dist[up[u][l]] == d[v] - d[up[u][l]]) u = up[u][l];
        }
        update(u, dist[u]);
        ans.pb(u);
    }
    sort(all(ans));
    cout << sz(ans) << '\n';
    for(auto v : ans) cout << v << " ";
}

signed main() {
    tout[0] = inf;
    d[0] = -inf;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 93164 KB Output is correct
2 Correct 266 ms 93192 KB Output is correct
3 Correct 267 ms 93108 KB Output is correct
4 Correct 363 ms 100868 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12628 KB Output is correct
2 Correct 8 ms 12628 KB Output is correct
3 Correct 483 ms 77092 KB Output is correct
4 Correct 469 ms 79512 KB Output is correct
5 Correct 627 ms 76572 KB Output is correct
6 Correct 761 ms 79688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 7 ms 12372 KB Output is correct
3 Correct 7 ms 12312 KB Output is correct
4 Correct 7 ms 12328 KB Output is correct
5 Correct 7 ms 12372 KB Output is correct
6 Correct 8 ms 12372 KB Output is correct
7 Correct 7 ms 12244 KB Output is correct
8 Correct 8 ms 12304 KB Output is correct
9 Correct 7 ms 12280 KB Output is correct
10 Correct 7 ms 12372 KB Output is correct
11 Correct 6 ms 12244 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 7 ms 12244 KB Output is correct
14 Correct 7 ms 12372 KB Output is correct
15 Correct 7 ms 12372 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 77436 KB Output is correct
2 Correct 568 ms 77516 KB Output is correct
3 Correct 616 ms 81452 KB Output is correct
4 Correct 611 ms 76580 KB Output is correct
5 Correct 454 ms 68412 KB Output is correct
6 Correct 822 ms 84360 KB Output is correct
7 Correct 722 ms 83112 KB Output is correct
8 Correct 680 ms 82548 KB Output is correct
9 Correct 763 ms 76764 KB Output is correct
10 Correct 650 ms 76572 KB Output is correct
11 Correct 473 ms 78720 KB Output is correct
12 Correct 428 ms 82548 KB Output is correct
13 Correct 485 ms 84768 KB Output is correct
14 Correct 401 ms 80184 KB Output is correct
15 Correct 62 ms 23272 KB Output is correct
16 Correct 618 ms 71844 KB Output is correct
17 Correct 480 ms 75540 KB Output is correct
18 Correct 638 ms 70468 KB Output is correct
19 Correct 674 ms 87844 KB Output is correct
20 Correct 681 ms 89024 KB Output is correct
21 Correct 592 ms 83460 KB Output is correct
22 Correct 578 ms 83688 KB Output is correct