Submission #998733

#TimeUsernameProblemLanguageResultExecution timeMemory
998733NoLoveDžumbus (COCI19_dzumbus)C++14
0 / 110
255 ms18244 KiB
/** * author : Lăng Trọng Đạt * created: 14-06-2024 **/ #include <bits/stdc++.h> using namespace std; #define int long long void mi(int& a, int b) { if (b < a) a = b; } const int MAXN = 1000 + 5; vector<int> adj[MAXN]; int g[MAXN]; int n, m, a, b; int dp[MAXN][MAXN][2]; // 0 là chưa say // 1 là đã chia sẻ int sz[MAXN]; void dfs(int v, int prv) { dp[v][0][1] = g[v]; dp[v][0][0] = 0; sz[v] = 1; for (int u : adj[v]) { if (u == prv) continue; dfs(u, v); // t = 0 for (int k = sz[v] + sz[u]; k >= 0; k--) { for (int j = max(0LL, k - sz[v]); j <= min(k, sz[u]); j++) { mi(dp[v][k + 2][1], dp[v][k - j][0] + dp[u][j][0] + g[u] + g[v]); if (k - j != 0) mi(dp[v][k + 1][1], dp[v][k - j][1] + dp[u][j][0] + g[u]); if (j != 0) mi(dp[v][k + 1][1], dp[v][k - j][0] + dp[u][j][1] + g[v]); mi(dp[v][k][0], min(dp[v][k - j][0], dp[v][k - j][1]) + min(dp[u][j][1], dp[u][j][0])); } } sz[v] += sz[u]; } } main() { // freopen("hi.inp", "r", stdin); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> g[i]; } for (int i = 1; i <= m; i++) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } memset(dp, 0x3f, sizeof(dp)); dfs(1, -1); map<int, int> mp; mp[-1] = 0; auto add = [&](int s, int i) -> void { if (mp.count(s)) mp[s] = max(mp[s], i); else mp[s] = i; }; for (int i = 1; i <= n; i++) { add(dp[1][i][0], i); add(dp[1][i][1], i); } int q, x; cin >> q; for (int i = 1; i <= q; i++) { cin >> x; auto it = mp.upper_bound(x); cout << prev(it)->second << "\n"; } }

Compilation message (stderr)

dzumbus.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...