Submission #981044

#TimeUsernameProblemLanguageResultExecution timeMemory
981044hqminhuwuDžumbus (COCI19_dzumbus)C++14
110 / 110
37 ms15188 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" const int N = 1e3 + 5; const ll oo = 1e9; const ll mod = 1e9 + 7; // 998244353; int dp[N][3][N], d[N], sz[N], ans[N]; vector <int> a[N]; void minz (int &u, int v){ if (u > v) u = v; } void dfs (int u, int p){ dp[u][0][0] = 0; dp[u][1][1] = d[u]; sz[u] = 1; for (int v : a[u]) if (v != p){ dfs(v, u); ford (i, sz[u], 0) forr (j, 0, sz[v]){ minz(dp[u][0][i + j], dp[u][0][i] + dp[v][0][j]); minz(dp[u][1][i + j], dp[u][1][i] + dp[v][0][j]); minz(dp[u][2][i + j], min(dp[u][1][i] + min(dp[v][1][j], dp[v][2][j]), dp[u][2][i] + min(dp[v][0][j], min(dp[v][1][j], dp[v][2][j])))); } sz[u] += sz[v]; forr (i, 0, sz[u]){ minz(dp[u][1][i], dp[u][2][i]); minz(dp[u][0][i], dp[u][2][i]); } } } int n, m, q, u, v; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n >> m; forr (i, 1, n) cin >> d[i]; forr (i, 1, m){ cin >> u >> v; a[u].pb(v); a[v].pb(u); } memset (dp, 63, sizeof dp); memset (ans, 63, sizeof ans); int cur = 0; ans[0] = 0; forr (i, 1, n) if (dp[i][0][0]){ dfs(i, i); ford (j, cur, 0) ford (k, sz[i], 0) minz(ans[j + k], ans[j] + dp[i][0][k]); cur += sz[i]; } cin >> q; while (q--){ cin >> u; int k = upper_bound(ans + 1, ans + 1 + n, u) - ans - 1; cout << k << "\n"; } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...