| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 381465 |
2021-03-25T08:12:14 Z |
kartel |
Pastiri (COI20_pastiri) |
C++14 |
|
792 ms |
113900 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)], 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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
303 ms |
113900 KB |
Output is correct |
| 2 |
Incorrect |
151 ms |
27884 KB |
Sheep 25 not protected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
13164 KB |
Output is correct |
| 2 |
Correct |
33 ms |
12908 KB |
Output is correct |
| 3 |
Correct |
752 ms |
75116 KB |
Output is correct |
| 4 |
Correct |
762 ms |
77548 KB |
Output is correct |
| 5 |
Correct |
776 ms |
75244 KB |
Output is correct |
| 6 |
Correct |
792 ms |
78700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
375 ms |
28268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
