oj.uz

Submission #1110899

# Submission time Handle Problem Language Result Execution time Memory
1110899 2024-11-10T23:52:02 Z vincentbucourt1 Nile (IOI24_nile) C++17
32 / 100
 90 ms 21028 KB 
#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // change int to ll

struct Query {
  ll val, idx;
};
bool cmpQuery (const Query& a, const Query& b) {
  return a.val < b.val;
};

struct Edge {
  ll weight, u, v;
};
bool cmpEdge (const Edge& a, const Edge& b) {
  return a.weight < b.weight;
}

const ll INF = 1e18;

ll N, Q;
vector<pair<ll, ll>> weight;
vector<ll> solo, duo;
vector<Query> queries;
vector<Edge> edges;

vector<ll> ans;

struct DSU {
  vector<ll> info;
  ll cost;
  vector<ll> diffOdd, diffEven, allDuo;
  DSU (ll n) {
    info.assign(n, -1);
    diffOdd.resize(N), diffEven.resize(N), allDuo.resize(N);
    cost = 0;
    for (ll iVal = 0; iVal < N; iVal++) {
      cost += solo[iVal];
      diffOdd[iVal] = solo[iVal] - duo[iVal];
      diffEven[iVal] = INF;
      allDuo[iVal] = duo[iVal];
    }
  }
  ll get (ll node) {
    return (info[node] < 0 ? node : info[node] = get(info[node]));
  }
  bool sameCC (ll u, ll v) {
    return get(u) == get(v);
  }
  ll sizeCC (ll u) {
    return -info[get(u)];
  }
  ll getDiff (ll node) {
    node = get(node);
    ll ans = allDuo[node];
    if (sizeCC(node) % 2 == 1) {
      ans += diffOdd[node];
    }
    return ans;
  }
  bool merge (ll u, ll v) {
    ll initU = u, initV = v;
    u = get(u), v = get(v);

    if (abs(initU - initV) == 2) {
      // assert(sameCC(u, v));
      ll mid = min(initU, initV) + 1;
      cost -= diffOdd[u];
      diffOdd[u] = min(diffOdd[u], solo[mid] - duo[mid]);
      diffEven[u] = min(diffEven[u], solo[mid] - duo[mid]);
      cost += diffOdd[u];
    }

    if (u == v) return false;
    // assert(get(u) != get(v));

    cost -= getDiff(u);
    cost -= getDiff(v);

    if (u > v) swap(u, v);
    if (sizeCC(u) % 2 == 1) {
      diffOdd[u] = min(diffOdd[u], diffEven[v]);
      diffEven[u] = min(diffEven[u], diffOdd[v]);
    }
    else {
      diffOdd[u] = min(diffOdd[u], diffOdd[v]);
      diffEven[u] = min(diffEven[u], diffEven[v]);
    }
    allDuo[u] += allDuo[v];

    info[u] += info[v];
    info[v] = u;
    cost += getDiff(u);
    // assert(get(v) == u);
    return true;
  }
  ll getCost () {
    return cost;
  }
};

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
  N = A.size();
  Q = E.size();
  weight.resize(N), solo.resize(N), duo.resize(N);
  queries.resize(Q);
  for (ll iVal = 0; iVal < N; iVal++) {
    weight[iVal] = {W[iVal], iVal};
  }
  sort(weight.begin(), weight.end());
  for (ll iVal = 0; iVal < N; iVal++) {
    solo[iVal] = A[weight[iVal].second];
    duo[iVal] = B[weight[iVal].second];
  }
  for (ll iQuery = 0; iQuery < Q; iQuery++) {
    queries[iQuery] = {E[iQuery], iQuery};
  }
  sort(queries.begin(), queries.end(), cmpQuery);

  for (ll iVal = 0; iVal < N-1; iVal++) {
    edges.push_back({weight[iVal+1].first - weight[iVal].first, iVal, iVal+1});
    // assert(weight[iVal+1].first - weight[iVal].first >= 0);
    if (iVal < N-2) {
      edges.push_back({weight[iVal+2].first - weight[iVal].first, iVal, iVal+2});
      // assert(weight[iVal+2].first - weight[iVal].first >= 0);
    }
  }
  sort(edges.begin(), edges.end(), cmpEdge);

  DSU dsu (N+1);
  ans.resize(Q);

  ll iEdge = 0;
  for (ll iQuery = 0; iQuery < Q; iQuery++) {
    ll qDiff = queries[iQuery].val;
    ll qIdx = queries[iQuery].idx;
    while (iEdge < (ll) (edges.size()) && edges[iEdge].weight <= qDiff) {
      dsu.merge(edges[iEdge].u, edges[iEdge].v);
      iEdge++;
    }
    ans[qIdx] = dsu.getCost();
  }

  return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15028 KB Output is correct
2 Correct 42 ms 15032 KB Output is correct
3 Correct 41 ms 15084 KB Output is correct
4 Incorrect 41 ms 15040 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14996 KB Output is correct
2 Correct 46 ms 15040 KB Output is correct
3 Correct 50 ms 14996 KB Output is correct
4 Correct 55 ms 15032 KB Output is correct
5 Correct 45 ms 15032 KB Output is correct
6 Correct 60 ms 16568 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14996 KB Output is correct
2 Correct 46 ms 15040 KB Output is correct
3 Correct 50 ms 14996 KB Output is correct
4 Correct 55 ms 15032 KB Output is correct
5 Correct 45 ms 15032 KB Output is correct
6 Correct 60 ms 16568 KB Output is correct
7 Correct 77 ms 20784 KB Output is correct
8 Correct 75 ms 20912 KB Output is correct
9 Correct 90 ms 20920 KB Output is correct
10 Correct 77 ms 20920 KB Output is correct
11 Correct 86 ms 21028 KB Output is correct
12 Correct 81 ms 20912 KB Output is correct
13 Correct 76 ms 20836 KB Output is correct
14 Correct 66 ms 20576 KB Output is correct
15 Correct 79 ms 20884 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -