| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 221947 | Haunted_Cpp | Džumbus (COCI19_dzumbus) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
author: Haunted_Cpp
*/
#include <cstdio>
#include <algorithm>
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 1e3 + 5;
const int DUMMY = 0;
const long long INF = 1e15 + 5;
long long dp [N][N][2];
long long cost [N];
int sub [N];
vector<int> g [N];
bool vis [N];
void join (int node, int p = -1) {
vis[node] = true;
for (auto to : g[node]) {
if (!vis[to]) {
vis[to] = true;
join (to, node);
}
}
}
// DP[NODE][SCORE][IS_VALID]
// IS_VALID - denotes if the connected component ending at node i has 2 or more nodes
void dfs (int node = 0, int p = -1) {
dp[node][0][0] = 0;
sub[node] = 1;
for (auto to : g[node]) {
if (to == p) continue;
dfs (to, node);
sub[node] += sub[to];
// USE
for (int i = sub[node]; i >= 2; i--) {
for (int j = i; j >= 0; j--) {
dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j][1]);
dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j][0]);
if (i - j - 1 >= 0 && j - 1 >= 0) {
dp[node][i][1] = min (dp[node][i][1], dp[node][i - j - 1][0] + cost[node] + dp[to][j - 1][0] + cost[to]);
}
if (j - 1 >= 0) {
dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j - 1][0] + cost[to]);
}
if (i - j - 1 >= 0) {
dp[node][i][1] = min (dp[node][i][1], dp[node][i - j - 1][0] + cost[node] + dp[to][j][1]);
}
}
}
// NOT USE
for (int i = sub[node]; i >= 2; i--) {
for (int j = i; j >= 0; j--) {
dp[node][i][0] = min (dp[node][i][0], dp[node][i - j][0] + min (dp[to][j][0], dp[to][j][1]));
}
}
}
}
int main () {
int n, m;
scanf ("%d %d", &n, &m);
cost[0] = INF;
for (int i = 1; i <= n; i++) scanf ("%lld", &cost[i]);
for (int i = 0; i < m; i++) {
int st, et;
scanf ("%d %d", &st, &et);
g[st].emplace_back(et);
g[et].emplace_back(st);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
g[DUMMY].emplace_back(i);
join (i);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j][0] = dp[i][j][1] = INF;
}
}
dfs ();
int q;
scanf ("%d", &q);
vector<pair<int, int> > perguntas (q);
for (int i = 0; i < q; i++) {
scanf ("%d", &perguntas[i].first);
perguntas[i].second = i;
}
sort (perguntas.begin(), perguntas.end());
vector<pair<long long, int> > Get (N);
for (int i = 0; i < N; i++) {
Get[i] = {dp[0][i][0], i};
}
sort (Get.begin(), Get.begin() + n + 1);
int pergunta_atual = 0;
int mx = 0;
vector<int> ans (q);
for (int i = 0; i < q; i++) {
while (pergunta_atual < N && Get[pergunta_atual].first <= perguntas[i].first) {
mx = max (mx, Get[pergunta_atual].second);
++pergunta_atual;
}
ans[perguntas[i].second] = mx;
}
for (int i = 0; i < q; i++) printf ("%d\n", ans[i]);
return 0;
}