oj.uz

Submission #381598

# Submission time Handle Problem Language Result Execution time Memory
381598 2021-03-25T10:45:46 Z NONAME Pastiri (COI20_pastiri) C++17
0 / 100
 1000 ms 106336 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);}
template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);}

const int man = (int)(5e5 + 500);

int n, m, timer;
int a[man], tin[man], tout[man], h[man], dp[man], pr[man];
int up[man][20];
bool gd;
vector <int> vc, g[man], all;

inline void cls() {
    vc.clear();
    gd = false;
    timer = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 20; ++j) {
            up[i][j] = -1;
        }
        h[i] = 0;
        g[i].clear();
        tin[i] = tout[i] = 0;
    }
}

void dfs(int v, int pr) {
    tin[v] = timer++;
    up[v][0] = pr;
    for (int i = 1; i < 20; ++i) {
        if (up[v][i - 1] != -1) {
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
    }
    for (auto& u : g[v]) {
        if (u == pr) {
            continue;
        }
        h[u] = h[v] + 1;
        dfs(u, v);
    }
    tout[v] = timer++;
}

bool upper(int v, int u) {
    return ((tin[v] <= tin[u]) && (tout[v] >= tout[u]));
}

int lca(int v, int u) {
    if (upper(v, u)) {
        return v;
    }
    if (upper(u, v)) {
        return u;
    }

    for (int i = 19; i >= 0; --i) {
        if ((up[v][i] != -1) && !upper(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}

void solve() {
    cls();

    cin >> n >> m;
    for (int i = 0; i < (n - 1); ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;

        gd &= (abs(x - y) == 1);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        --a[i];
    }

    if (gd) {
        sort(a, a + m);
        for (int i = 0; i < m; ++i) {
            if (i == (m - 1)) {
                vc.push_back(a[i]);
            } else {
                int md = (a[i] + a[i + 1]) >> 1;
                vc.push_back(md);
                if (abs(a[i] - md) == abs(a[i + 1] - md)) {
                    ++i;
                }
            }
        }
    } else {
        dfs(0, -1);

        for (int i = 0; i < n; ++i) {
            int mn = 1e9;
            for (int j = 0; j < m; ++j) {
                mn = min(mn, h[i] + h[a[j]] - 2 * h[lca(i, a[j])]);
            }

            int msk = 0;
            for (int j = 0; j < m; ++j) {
                if ((h[i] + h[a[j]] - (2 * h[lca(i, a[j])])) == mn) {
                    msk |= (1 << j);
                }
            }

            all.push_back(msk);
        }
        sort(all.begin(), all.end());
        all.resize(unique(all.begin(), all.end()) - all.begin());

        for (int msk = 0; msk < (1 << m); ++msk) {
            dp[msk] = 1e9;
        }
        dp[0] = 0;
        for (int msk = 0; msk < (1 << m); ++msk) {
            for (int i = 0; i < (int)(all.size()); ++i) {
                int nmsk = msk | all[i];
                if (chmin(dp[nmsk], dp[msk] + 1)) {
                    pr[nmsk] = msk;
                }
            }
        }

        int msk = (1 << m) - 1;
        while (msk > 0) {
            int need = msk ^ pr[msk];
            int p = -1;
            for (int i = 0; i < n; ++i) {
                int mn = 1e9;
                for (int j = 0; j < m; ++j) {
                    mn = min(mn, h[i] + h[a[j]] - 2 * h[lca(i, a[j])]);
                }

                int curMsk = 0;
                for (int j = 0; j < m; ++j) {
                    if ((h[i] + h[a[j]] - (2 * h[lca(i, a[j])])) == mn) {
                        curMsk |= (1 << j);
                    }
                }

                if ((curMsk & need) == need) {
                     p = i;
                     break;
                }
            }
            assert(p != -1);
            vc.push_back(p);
            msk = pr[msk];
        }
    }

    sort(vc.begin(), vc.end());
    cout << (int)(vc.size()) << "\n";
    for (auto& i : vc) {
        cout << (i + 1) << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    #ifdef _LOCAL
        system("color a");
        freopen("in.txt", "r", stdin);
        cin >> t;
    #endif

    for (int i = 1; i <= t; ++i) {
        cerr << "Case #" << i << ": \n";
        solve();
        cerr << "\n";
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 106336 KB Output is correct
2 Execution timed out 1083 ms 104924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13036 KB Output is correct
2 Correct 55 ms 12908 KB Output is correct
3 Execution timed out 1090 ms 74084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 24940 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1102 ms 73580 KB Time limit exceeded
2 Halted 0 ms 0 KB -