Submission #714033

#	Time	Username	Problem	Language	Result	Execution time	Memory
714033		KiriLL1ca	Pastiri (COI20_pastiri)	C++17	0 / 100	1090 ms	146792 KiB

pastiri

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc 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 vec vector
#define endl '\n'

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

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; }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e5 + 10;
vec <int> g[N];
int up[N][20], tin[N], tout[N], tim = 0;
int d[N];
inline void dfs (int v, int p) {
    tin[v] = tim++;
    up[v][0] = p;
    for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto u : g[v]) {
        if (u != p) {
            d[u] = d[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = tim++;
}
inline bool is (int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
inline int lca (int a, int b) {
    if (is(a, b)) return a;
    if (is(b, a)) return b;
    for (int i = 19; ~i; --i) if (!is(up[a][i], b)) a = up[a][i];
    return up[a][0];
}
inline int dis (int a, int b) { return d[a] + d[b] - 2 * d[lca(a, b)]; }

inline void solve () {
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        g[u].pb(v); g[v].pb(u);
    }
    dfs(0, 0);
    vec <int> a (k);
    for (auto &i : a) cin >> i, --i;

    queue <int> q;
    vec <int> dist (n, -1);
    for (auto i : a) {
        q.push(i);
        dist[i] = 0;
    }
    while (sz(q)) {
        int v = q.front(); q.pop();
        for (auto u : g[v]) {
            if (!~dist[u]) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    set <tuple <int, int, vec <int>>> urugvai;
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        vec <int> sis;
        for (int j = 0; j < k; ++j) {
            if (dis(i, a[j]) == dist[i]) {
                ++cnt;
                sis.pb(j);
            }
        }
        urugvai.insert({cnt, i, sis});
    }

    vec <bool> used (k);
    vec <int> ans;
    while (true) {
        pair <int, tuple <int, int, vec <int>>> mx = {-1, {0, 0, {}}};
        for (auto [_, v, sis] : urugvai) {
            int cnt = 0;
            for (auto i : sis) cnt += !used[i];
            umax(mx, {cnt, {_, v, sis}});
        }
        if (mx.fr < 1) break;
        for (auto i : get<2>(mx.sc)) used[i] = 1;
        ans.pb(get<1>(mx.sc));
        urugvai.erase(mx.sc);
    }

    cout << sz(ans) << endl;
    for (auto i : ans) cout << i + 1 << " ";
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51