Submission #1190846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190846		zNatsumi	Džumbus (COCI19_dzumbus)	C++20	50 / 110	33 ms	24900 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], f[u][i] + h[v][j], f[u][i] + f[v][j], h[u][i] + f[v][j]});
        if(i > 1) f[u][i + j] = min(f[u][i + j], f[u][i] + g[v][j]);
        if(i < sz[u] && i != 1) 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);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  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);
//    cerr << u << " " << sz[u] << "\n";
//    for(int i = 2; i <= sz[u]; i++) cerr << f[u][i] << " " << g[u][i] << "\n";
//    cerr << "\n";

    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];
  }
//  for(int i = 1; i <= n; i++) cerr << dp[i] << " \n"[i == n];

  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: 0 / 30
• Subtask 4: 0 / 30