oj.uz

Submission #714490

# Submission time Handle Problem Language Result Execution time Memory
714490 2023-03-24T17:05:50 Z nifeshe Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 100768 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, int)> update = [&](int v, int dst, int p) {
        used[v] = 1;
        if(dst == 0) return;
        for(auto to : g[v]) {
            if(to == p || (used[to] && c[to]) || (dist[to] != dist[v] - 1)) continue;
            update(to, dst - 1, v);
        }
    };
    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], 0);
        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 233 ms 93268 KB Output is correct
2 Correct 266 ms 93172 KB Output is correct
3 Correct 275 ms 93176 KB Output is correct
4 Correct 358 ms 100768 KB Output is correct

Subtask #2
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 475 ms 77156 KB Output is correct
4 Correct 500 ms 79484 KB Output is correct
5 Correct 590 ms 76744 KB Output is correct
6 Execution timed out 1077 ms 80200 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 77428 KB Output is correct
2 Correct 689 ms 77380 KB Output is correct
3 Correct 809 ms 81332 KB Output is correct
4 Correct 622 ms 76572 KB Output is correct
5 Correct 496 ms 68516 KB Output is correct
6 Correct 651 ms 84256 KB Output is correct
7 Correct 712 ms 83136 KB Output is correct
8 Correct 752 ms 82536 KB Output is correct
9 Correct 748 ms 76668 KB Output is correct
10 Correct 625 ms 83272 KB Output is correct
11 Correct 489 ms 85240 KB Output is correct
12 Correct 437 ms 90536 KB Output is correct
13 Correct 493 ms 92704 KB Output is correct
14 Correct 389 ms 86808 KB Output is correct
15 Correct 71 ms 24372 KB Output is correct
16 Execution timed out 1090 ms 77920 KB Time limit exceeded
17 Halted 0 ms 0 KB -