Submission #877212

#	Time	Username	Problem	Language	Result	Execution time	Memory
877212		adaawf	Pastiri (COI20_pastiri)	C++17	8 / 100	1033 ms	42392 KiB

pastiri

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int f[500005], d[500005], dd[500005], ff[500005], gg[500005];
vector<int> g[500005];
void dfs(int x, int p, int z, int c) {
    if (f[x] > c) {
        f[x] = c;
        d[x] = 0;
    }
    if (f[x] == c) d[x] |= (1 << z);
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x, z, c + 1);
    }
}
int main() {
    int n, k, c = 0;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        if (abs(u - v) == 1) c++;
    }
    vector<int> v;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    if (c == n - 1) {
        f[1] = 1;
        gg[1] = 1;
        ff[1] = v[0];
        for (int i = 2; i <= k; i++) {
            f[i] = 1e9;
            if (v[i - 1] % 2 == v[i - 2] % 2) {
                if (f[i] > f[i - 2] + 1) {
                    f[i] = f[i - 2] + 1;
                    ff[i] = (v[i - 1] + v[i - 2]) / 2;
                    gg[i] = 2;
                }
            }
            if (f[i] > f[i - 1] + 1) {
                f[i] = f[i - 1] + 1;
                ff[i] = v[i - 1];
                gg[i] = 1;
            }
        }
        cout << f[k] << '\n';
        int h = k;
        while (h) {
            cout << ff[h] << " ";
            h = h - gg[h];
        }
        return 0;
    }
    if (k <= 15) {
        for (int i = 1; i <= n; i++) {
            f[i] = 1e9;
        }
        for (int i = 0; i < k; i++) {
            dfs(v[i], -1, i, 0);
        }
        for (int i = 1; i <= n; i++) {
            dd[d[i]] = i;
        }
        for (int i = 1; i < (1 << k); i++) f[i] = 1e9;
        for (int i = 0; i < (1 << k); i++) {
            if (f[i] == 1e9) continue;
            for (int j = 1; j < (1 << k); j++) {
                if (dd[j] == 0) continue;
                int h = (i | j);
                if (f[h] > f[i] + 1) {
                    f[h] = f[i] + 1;
                    ff[h] = dd[j];
                    gg[h] = i;
                }
            }
        }
        cout << f[(1 << k) - 1] << '\n';
        int h = (1 << k) - 1;
        while (h) {
            cout << ff[h] << " ";
            h = gg[h];
        }
        return 0;
    }
}

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