Submission #229218

#TimeUsernameProblemLanguageResultExecution timeMemory
229218VEGAnnDžumbus (COCI19_dzumbus)C++14
110 / 110
148 ms19260 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() #define MP make_pair #define PB push_back #define ft first #define sd second #define pii pair<ll, ll> #define sz(x) ((ll)x.size()) using namespace std; typedef long long ll; const ll N = 1010; const ll oo = 1e18; vector<ll> g[N]; ll n, siz[N], f[N][N][3], ff[N][N][3], res[N], a[N], m, rez[N]; bool mrk[N]; void calc(ll v, ll p){ mrk[v] = 1; siz[v] = 1; for (ll u : g[v]){ if (u == p) continue; calc(u, v); siz[v] += siz[u]; } for (ll it = 0; it < 2; it++) for (ll i = 0; i <= siz[v]; i++) f[v][i][it] = oo; f[v][0][0] = 0; ll csz = 1; for (ll u : g[v]){ if (u == p) continue; for (ll it = 0; it < 2; it++) for (ll i = 0; i <= csz; i++) ff[v][i][it] = f[v][i][it]; for (ll k = 0; k <= siz[u]; k++){ // cerr << u << " " << f[u][k][0] << " " << f[u][k][1] << '\n'; ll mn = min(f[u][k][0], f[u][k][1]); if (mn == oo) continue; for (ll kol = csz; kol >= 0; kol--){ // cerr << kol << '\n'; if (ff[v][kol][0] != oo) f[v][kol + k][0] = min(f[v][kol + k][0], ff[v][kol][0] + mn); if (ff[v][kol][0] != oo && f[u][k][0] + a[u] < oo) f[v][kol + k + 2][1] = min(f[v][kol + k + 2][1], ff[v][kol][0] + f[u][k][0] + a[v] + a[u]); if (ff[v][kol][0] != oo && f[u][k][1] < oo) f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][0] + f[u][k][1] + a[v]); if (ff[v][kol][1] != oo) f[v][kol + k][1] = min(f[v][kol + k][1], ff[v][kol][1] + mn); if (ff[v][kol][1] != oo && f[u][k][0] + a[u] < oo) f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][1] + f[u][k][0] + a[u]); } } csz += siz[u]; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> m; for (ll i = 0; i < n; i++) cin >> a[i]; for (ll i = 0; i < m; i++){ ll x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); } fill(res, res + N, oo); res[0] = 0; for (ll i = 0; i < n; i++){ if (mrk[i]) continue; calc(i, -1); for (ll i = 0; i < N; i++) rez[i] = res[i]; for (ll k = 1; k <= siz[i]; k++) for (ll j = n; j - k >= 0; j--) if (res[j - k] != oo) res[j] = min(res[j], rez[j - k] + min(f[i][k][0], f[i][k][1])); } ll qq; cin >> qq; for (; qq; qq--){ ll x; cin >> x; for (ll i = n; i >= 0; i--) if (res[i] <= x){ cout << i << '\n'; break; } } 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...