oj.uz

Submission #877217

# Submission time Handle Problem Language Result Execution time Memory
877217 2023-11-23T03:57:39 Z adaawf Pastiri (COI20_pastiri) C++14
8 / 100
 1000 ms 41760 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() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    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);
        }
        vector<int> vv;
        for (int i = 1; i <= n; i++) {
            if (dd[d[i]] == 0) {
                vv.push_back(d[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 : vv) {
                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 94 ms 32684 KB Output is correct
2 Correct 95 ms 32592 KB Output is correct
3 Correct 96 ms 32692 KB Output is correct
4 Correct 147 ms 37560 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19288 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 756 ms 35508 KB Output is correct
4 Correct 768 ms 41760 KB Output is correct
5 Execution timed out 1041 ms 37636 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 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 214 ms 28752 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -