oj.uz

Submission #381444

# Submission time Handle Problem Language Result Execution time Memory
381444 2021-03-25T07:59:29 Z kartel Pastiri (COI20_pastiri) C++14
0 / 100
 1000 ms 114076 KB 
#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)];
int tin[N], tout[N], up[N][21], dp[N], a[N];
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);
    }

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

    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 mask = 1; mask < (1 << k); mask++) {
        if (__builtin_popcount(mask) == 1) {
            for (int i = 0; i < k; i++) {
                if (!(mask & (1 << i))) {
                    continue;
                }
                can[mask] = a[i];
                break;
            }

            continue;
        }

        int mx = 0;

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

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

                if (i == j) {
                    continue;
                }

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

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

        int hv = -1;

        for (int i = 0; i < k; i++) {
            if (!(mask & (1 << 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 & (1 << 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[(1 << k) - 1] << el;

    int mask = (1 << 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.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 114076 KB Output is correct
2 Execution timed out 1106 ms 113968 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 13292 KB Output is correct
2 Correct 137 ms 12908 KB Output is correct
3 Execution timed out 1000 ms 75176 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 12396 KB Sheep 9 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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