oj.uz

Submission #833962

# Submission time Handle Problem Language Result Execution time Memory
833962 2023-08-22T09:48:53 Z vjudge1 Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 109340 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 185 ms 99792 KB Output is correct
2 Correct 214 ms 99748 KB Output is correct
3 Correct 215 ms 99708 KB Output is correct
4 Correct 310 ms 109340 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12752 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 421 ms 83800 KB Output is correct
4 Correct 396 ms 86152 KB Output is correct
5 Correct 518 ms 83156 KB Output is correct
6 Execution timed out 1083 ms 86884 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12364 KB Output is correct
2 Correct 6 ms 12372 KB Output is correct
3 Correct 8 ms 12416 KB Output is correct
4 Correct 7 ms 12292 KB Output is correct
5 Correct 7 ms 12380 KB Output is correct
6 Correct 6 ms 12292 KB Output is correct
7 Correct 6 ms 12364 KB Output is correct
8 Correct 6 ms 12356 KB Output is correct
9 Correct 6 ms 12372 KB Output is correct
10 Correct 7 ms 12372 KB Output is correct
11 Correct 7 ms 12236 KB Output is correct
12 Correct 6 ms 12232 KB Output is correct
13 Correct 7 ms 12336 KB Output is correct
14 Correct 6 ms 12368 KB Output is correct
15 Correct 6 ms 12364 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 84116 KB Output is correct
2 Correct 530 ms 84108 KB Output is correct
3 Correct 592 ms 89264 KB Output is correct
4 Correct 516 ms 83216 KB Output is correct
5 Correct 383 ms 75068 KB Output is correct
6 Correct 587 ms 92948 KB Output is correct
7 Correct 621 ms 91224 KB Output is correct
8 Correct 598 ms 90392 KB Output is correct
9 Correct 667 ms 83408 KB Output is correct
10 Correct 500 ms 83212 KB Output is correct
11 Correct 387 ms 85340 KB Output is correct
12 Correct 347 ms 90644 KB Output is correct
13 Correct 368 ms 93328 KB Output is correct
14 Correct 293 ms 86824 KB Output is correct
15 Correct 51 ms 24300 KB Output is correct
16 Execution timed out 1078 ms 77896 KB Time limit exceeded
17 Halted 0 ms 0 KB -