Submission #1190875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190875		zNatsumi	Džumbus (COCI19_dzumbus)	C++20	110 / 110	32 ms	24904 KiB

dzumbus

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int32_t N = 1e3 + 5;
const int64_t INF = 1e17;

int n, m, q, d[N], f[N][N], g[N][N], h[N][N], dp[N], sz[N];
bool vst[N];
vector<int> ad[N];

void dfs(int u){
  vst[u] = true;
  h[u][1] = f[u][1] = d[u];

  sz[u] = 1;
  for(auto v : ad[u]) if(!vst[v]){
    dfs(v);
    for(int i = sz[u]; i >= 0; i--)
      for(int j = sz[v]; j >= 1; j--){
        if(i >= 1) f[u][i + j] = min(f[u][i + j], min(f[u][i], h[u][i]) + min(f[v][j], h[v][j]));
        if(i > 1) f[u][i + j] = min(f[u][i + j], f[u][i] + g[v][j]);
        if(i < sz[u]) g[u][i + j] = min({g[u][i + j], g[u][i] + f[v][j], g[u][i] + g[v][j]});
      }
    for(int i = sz[u]; i >= 1; i--)
      for(int j = sz[v]; j >= 1; j--)
        h[u][i + j] = min(h[u][i + j], h[u][i] + g[v][j]);

    sz[u] += sz[v];
  }
  f[u][1] = INF;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> d[i];
  for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  for(int i = 1; i <= n; i++){
    dp[i] = INF;
    for(int j = 1; j <= n; j++) f[i][j] = g[i][j] = h[i][j] = INF;
  }
  int cur = 0;
  for(int u = 1; u <= n; u++) if(!vst[u]){
    dfs(u);
    for(int i = cur; i >= 0; i--) if(i != 1)
      for(int j = sz[u]; j >= 2; j--)
        dp[i + j] = min(dp[i + j], dp[i] + min(f[u][j], g[u][j]));
    cur += sz[u];
  }
  cin >> q;
  while(q--){
    int s; cin >> s;
    int it = upper_bound(dp + 1, dp + n + 1, s) - dp - 1;
    cout << (it < 2 ? 0 : it) << "\n";
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30