Submission #1247162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247162		julia_08	Džumbus (COCI19_dzumbus)	C++20	50 / 110	44 ms	29100 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct event{

  ll x; int t, i; 

  bool operator < (event other){
    if(x != other.x) return x < other.x;
    if(t != other.t) return t < other.t;
    return i < other.i;
  }

};

const int MAXN = 1e3 + 10;
const int MAXQ = 2e5 + 10;

const ll INF = 1e18;

int d[MAXN], marc[MAXN], sub[MAXN];

int ans[MAXQ];

ll dp[MAXN][MAXN][3];

vector<int> adj[MAXN];

int n, m; 

void init(int v){

  sub[v] = 1;

  for(int i=0; i<=n; i++) dp[v][i][0] = dp[v][i][1] = dp[v][i][2] = INF;

  dp[v][0][0] = 0;
  dp[v][0][2] = d[v];

}

void merge(int u, int v){

  for(int i=sub[v]; i>=0; i--){
    for(int j=sub[u]; j>=0; j--){
        
      dp[v][i + j][0] = min(dp[v][i + j][0], dp[v][i][0] + min({dp[u][j][0], dp[u][j][1], dp[u][j][2]}));

      dp[v][i + j][1] = min(dp[v][i + j][1], dp[v][i][1] + min({dp[u][j][0], dp[u][j][1], dp[u][j][2]}));

      dp[v][i + j + 1][1] = min(dp[v][i + j + 1][1], min(dp[v][i][1], dp[v][i][2]) + dp[u][j][2]);
      dp[v][i + j + 1][1] = min(dp[v][i + j + 1][1], dp[v][i][2] + min(dp[u][j][1], dp[u][j][2]));

      dp[v][i + j + 2][1] = min(dp[v][i + j + 2][1], dp[v][i][2] + dp[u][j][2]);

      dp[v][i + j][2] = min(dp[v][i + j][2], dp[v][i][2] + dp[u][j][0]);

    }
  }

  sub[v] += sub[u];

}

void dfs(int v){

  marc[v] = 1;

  init(v);

  for(auto u : adj[v]){
    if(!marc[u]){
      dfs(u);
      merge(u, v);
    }
  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for(int i=1; i<=n; i++) cin >> d[i];

  while(m--){
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<event> all_events;

  for(int i=1; i<=n; i++){
    if(!marc[i]){

      dfs(i);

      for(int j=1; j<=n; j++){
        all_events.push_back({min({dp[i][j][0], dp[i][j][1], dp[i][j][2]}), 0, i});
      }      

    }
  }

  int q; cin >> q;

  for(int i=1; i<=q; i++){
    int s; cin >> s;
    all_events.push_back({s, 1, i});
  }

  sort(all_events.begin(), all_events.end());

  int tot = 0;

  for(auto &ev : all_events){
    if(ev.t == 0){
      tot ++;
    } else ans[ev.i] = tot;
  }

  for(int i=1; i<=q; i++) cout << ans[i] << "\n";

  return 0;
}

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