Submission #381465

#	Time	Username	Problem	Language	Result	Execution time	Memory
381465		kartel	Pastiri (COI20_pastiri)	C++14	18 / 100	792 ms	113900 KiB

pastiri

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
//#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 5e5 + 500;

int can[(1 << 16)];
int f[(1 << 16)], prv[(1 << 16)], st[20];
int tin[N], tout[N], up[N][21], dp[N], a[N], dist[20][20];
int tim, n, k;
vector <int> g[N];

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

void dfs(int v, int pr, int d) {
    tin[v] = tim++;
    dp[v] = d;

    up[v][0] = pr;

    for (auto u : g[v]) {
        if (u == pr)
            continue;

        dfs(u, v, d + 1);
    }

    tout[v] = tim++;
}

int lca(int v, int u) {
    if (isa(v, u)) return v;
    if (isa(u, v)) return u;

    for (int st = 20; st >= 0; st--) {
        if (!isa(up[v][st], u)) {
            v = up[v][st];
        }
    }

    return up[v][0];
}

int dst(int v, int u) {return dp[v] + dp[u] - 2 * dp[lca(u, v)];}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> k;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[v].pb(u);
        g[u].pb(v);
    }

    st[0] = 1;

    for (int i = 0; i < k; i++) {
        cin >> a[i];
        st[i + 1] = st[i] * 2;
    }

    if (k > 15) {
        vector <int> dp(k + 1);
        vector <int> pred(k + 1);

        dp[0] = 0;

        for (int i = 1; i <= k; i++) {
            dp[i] = 1e9;
            if (i - 2 >= 0 && (a[i - 1] - a[i - 2]) % 2 == 0) {
                dp[i] = dp[i - 2] + 1;
                pred[i] = i - 2;
            }

            if (dp[i - 1] + 1 < dp[i]) {
                dp[i] = dp[i - 1] + 1;
                pred[i] = i - 1;
            }
        }

        vector <int> ans;

        cout << dp[k] << el;

        int i = k;
        while (i) {
            if (pred[i] == i - 1) {
                ans.pb(a[i - 1]);
            }
            else {
                ans.pb(a[i - 2] + (a[i - 1] - a[i - 2]) / 2);
            }
            i = pred[i];
        }

        sort(all(ans));

        assert(sz(ans) == dp[k]);

        for (auto x : ans) {
            cout << x << " ";
        }
        return 0;
    }

    tin[0] = tim++;

    dfs(1, 0, 0);

    tout[0] = tim++;

    for (int st = 1; st <= 20; st++) {
        for (int i = 1; i <= n; i++) {
            up[i][st] = up[up[i][st - 1]][st - 1];
        }
    }

    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            dist[i][j] = dst(a[i], a[j]);
        }
    }

    for (int mask = 1; mask < st[k]; mask++) {
        if (__builtin_popcount(mask) == 1) {
            for (int i = 0; i < k; i++) {
                if (!(mask & st[i])) {
                    continue;
                }
                can[mask] = a[i];
                break;
            }

            continue;
        }

        int mx = 0;

        for (int i = 0; i < k; i++) {
            if (!(mask & st[i])) {
                continue;
            }

            for (int j = 0; j < k; j++) {
                if (!(mask & st[j])) {
                    continue;
                }

                if (i == j) {
                    continue;
                }

                mx = max(mx, dist[i][j]);
            }
        }

        if (mx & 1) {
            can[mask] = -1;
            continue;
        }

        int hv = -1;

        for (int i = 0; i < k; i++) {
            if (!(mask & st[i])) {
                continue;
            }

            int d = mx / 2;
            int pr = a[i];

            for (int st = 20; st >= 0; st--) {
                if ((1 << st) & d) {
                    pr = up[pr][st];
                }
            }

            if (!pr) {
                continue;
            }

            int isall = 1;

            for (int j = 0; j < k; j++) {
                if (!(mask & st[j])) {
                    continue;
                }

                isall &= (dst(pr, a[j]) == mx / 2);
            }

            if (isall) {
                int mn = 1e9;
                for (int j = 0; j < k; j++) {
                    mn = min(mn, dst(a[j], pr));
                }

                if (mx / 2 == mn) {
                    hv = pr;
                }
            }
        }

        can[mask] = hv;
    }

    f[0] = 0;

    for (int mask = 1; mask < (1 << k); mask++) {
        f[mask] = 1e9;

        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if (can[sub] != -1) {
                if (f[mask ^ sub] + 1 < f[mask]) {
                    prv[mask] = sub;
                    f[mask] = f[mask ^ sub] + 1;
                }
            }
        }
    }

    vector <int> ans;

    cout << f[st[k] - 1] << el;

    int mask = st[k] - 1;

    while (mask) {
        ans.pb(can[prv[mask]]);
        mask ^= prv[mask];
    }

    sort(all(ans));

    for (auto x : ans) {
        cout << x << " ";
    }
}


/*

7
4 6 7 2 3 1 5
*/

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