# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
221940 | 2020-04-11T14:27:25 Z | Haunted_Cpp | Džumbus (COCI19_dzumbus) | C++17 | 1000 ms | 17400 KB |
#include <cstdio> #include <iostream> #include <vector> #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 current component ending at node i, has >= 2 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); while (q--) { int budget; scanf ("%d", &budget); int ans = 0; for (int i = N - 1; i >= 0; i--) { if (dp[0][i][0] <= budget) { ans = max (ans, i); break; } } printf ("%d\n", ans); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 573 ms | 16376 KB | Output is correct |
2 | Correct | 807 ms | 16512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 573 ms | 16376 KB | Output is correct |
2 | Correct | 807 ms | 16512 KB | Output is correct |
3 | Execution timed out | 1074 ms | 17400 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 232 ms | 17016 KB | Output is correct |
2 | Correct | 216 ms | 16760 KB | Output is correct |
3 | Correct | 259 ms | 16780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 573 ms | 16376 KB | Output is correct |
2 | Correct | 807 ms | 16512 KB | Output is correct |
3 | Execution timed out | 1074 ms | 17400 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |