Submission #233722

#TimeUsernameProblemLanguageResultExecution timeMemory
233722jungsnowDžumbus (COCI19_dzumbus)C++14
0 / 110
639 ms8312 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1005; int n, m, Q, S, dp[N][N], M[N], A[N], F[N][N]; vector<int> adj[N]; void dfs(int par, int u) { M[u] = A[u]; dp[u][A[u]] = 1; for (int v : adj[u]) if (v != par) { dfs(u, v); M[u] += M[v]; for (int j = M[u]; j > A[u]; j--) { for (int iv = min(j, M[v]); iv >= 0; iv--) { if (j - iv < A[u]) continue; dp[u][j] = max(dp[u][j], dp[v][iv] + dp[u][j - iv]); } } } } void getF(int par, int u) { int sum = 0; for (int v : adj[u]) if (v != par) { getF(u, v); sum += M[v]; for (int j = sum; j > 0; j--) { F[u][j] = max(F[u][j], dp[u][j]); for (int k = min(j, M[v]); k >= 0; k--) { F[u][j] = max(F[u][j], F[u][j - k] + (F[v][k]==1)?0:F[v][k]); } } } } int main() { // freopen("dzumbus.inp", "r", stdin); // freopen("dzumbus.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> A[i]; for (int u, v, i = 1; i <= m; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(0, 1); //cout << dp[1][14] << '\n'; getF(0, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j < N; j++) { F[i][j] = max(F[i][j], F[i][j - 1]); } } cin >> Q; while (Q--) { cin >> S; int c = 0; for (int i = 1; i <= n; i++) c = max(c, F[i][S]); if (c == 1) c = 0; cout << c << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...