Submission #1258176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258176		altern23	Nile (IOI24_nile)	C++20	0 / 100	43 ms	11956 KiB

nile

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

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second

const ll INF = 1e18;
ll ans = 0;

struct DSU{
  ll N;
  vector<ll> par, sz, mx, sum;
  DSU(ll _n){
    N = _n;
    par.resize(N + 5), sz.resize(N + 5), mx.resize(N + 5), sum.resize(N + 5);
    for(int i = 0; i < N; i++){
      par[i] = i;
      sz[i] = 1;
      mx[i] = -INF;
      sum[i] = 0;
    }
  }
  ll find(ll idx){
    return par[idx] == idx ? idx : par[idx] = find(par[idx]);
  }
  void join(ll a, ll b){
    a = find(a), b = find(b);
    if(a == b) return;
    ans -= sum[a] - (sz[a] % 2 ? mx[a] : 0LL);
    ans -= sum[b] - (sz[b] % 2 ? mx[b] : 0LL);
    if(sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b], sz[b] = 0;
    sum[a] += sum[b], sum[b] = 0;
    mx[a] = max(mx[a], mx[b]);
    ans += sum[a] - (sz[a] % 2 ? mx[a] : 0LL);
  }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, std::vector<int> E) {  
  int Q = (int)E.size(), N = (int)W.size();
  vector<ll> R(Q, 0);

  vector<pii> objects;
  for(int i = 0; i < N; i++) objects.push_back({W[i], i});
  sort(objects.begin(), objects.end());

  vector<pair<ll, pii>> edges;
  for(int i = 0; i < N; i++){
    if(i + 1 < N) edges.push_back({objects[i + 1].fi - objects[i].fi, {objects[i].sec, objects[i + 1].sec}});
    if(i + 2 < N) edges.push_back({objects[i + 2].fi - objects[i].fi, {objects[i].sec, objects[i + 2].sec}});
  }
  sort(edges.begin(), edges.end());
  vector<pii> queries;
  
  DSU dsu(N);
  for(int i = 0; i < N; i++){
    dsu.mx[i] = dsu.sum[i] = B[i] - A[i];
  }

  for(int i = 0; i < Q; i++) queries.push_back({E[i], i});
  sort(queries.begin(), queries.end());

  ll cur = 0;
  for(int i = 0; i < N; i++) ans += A[i];

  for(auto [val, idx] : queries){
    while(cur < N && edges[cur].fi <= val){
      dsu.join(edges[cur].sec.fi, edges[cur].sec.sec);
      cur++;
    }
    R[idx] = ans;
  }
  return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18