oj.uz

Submission #877212

# Submission time Handle Problem Language Result Execution time Memory
877212 2023-11-23T03:56:02 Z adaawf Pastiri (COI20_pastiri) C++17
8 / 100
 1000 ms 42392 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 36320 KB Output is correct
2 Correct 310 ms 36776 KB Output is correct
3 Correct 258 ms 36508 KB Output is correct
4 Correct 366 ms 42392 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 21340 KB Output is correct
2 Correct 175 ms 21316 KB Output is correct
3 Execution timed out 1033 ms 41464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12888 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 32692 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -