oj.uz

Submission #1113659

# Submission time Handle Problem Language Result Execution time Memory
1113659 2024-11-17T00:58:43 Z vincentbucourt1 Nile (IOI24_nile) C++17
38 / 100
 99 ms 21968 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, type;
};
bool cmpEdge (const Edge& a, const Edge& b) {
  if (a.weight < b.weight) {
    return true;
  }
  else if (a.weight > b.weight) {
    return false;
  }
  return a.type < b.type;
}

const ll INF = 1e18;

ll N, Q;
vector<ll> weight, 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;
  }
};

struct Pos {
  int idx, w, s, d;
};
bool cmpOrder (const Pos& a, const Pos& b) {
  if (a.w < b.w) {
    return true;
  }
  else if (a.w > b.w) return false;
  return (a.s - a.d < b.s - b.d);
}

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);
  vector<Pos> inp;
  inp.resize(N);
  queries.resize(Q);
  for (int i = 0; i < N; i++) {
    inp[i] = {i, W[i], A[i], B[i]};
  }
  sort(inp.begin(), inp.end(), cmpOrder);
  for (int i = 0; i < N; i++) {
    weight[i] = inp[i].w;
    solo[i] = inp[i].s;
    duo[i] = inp[i].d;
  }

  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] - weight[iVal], iVal, iVal+1, 1});
    // assert(weight[iVal+1] - weight[iVal] >= 0);
  }
  for (ll iVal = 0; iVal < N-2; iVal++) {
      edges.push_back({weight[iVal+2] - weight[iVal], iVal, iVal+2, 2});
      // assert(weight[iVal+2] - weight[iVal] >= 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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17840 KB Output is correct
2 Correct 47 ms 17840 KB Output is correct
3 Correct 53 ms 17916 KB Output is correct
4 Incorrect 46 ms 17840 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 48 ms 17840 KB Output is correct
2 Correct 50 ms 18096 KB Output is correct
3 Correct 59 ms 17840 KB Output is correct
4 Correct 60 ms 17832 KB Output is correct
5 Correct 56 ms 17824 KB Output is correct
6 Correct 56 ms 17816 KB Output is correct

Subtask #4
0.0 / 11.0

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

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 44 ms 17840 KB Output is correct
8 Correct 47 ms 17840 KB Output is correct
9 Correct 53 ms 17916 KB Output is correct
10 Incorrect 46 ms 17840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17840 KB Output is correct
2 Correct 50 ms 18096 KB Output is correct
3 Correct 59 ms 17840 KB Output is correct
4 Correct 60 ms 17832 KB Output is correct
5 Correct 56 ms 17824 KB Output is correct
6 Correct 56 ms 17816 KB Output is correct
7 Correct 70 ms 21936 KB Output is correct
8 Correct 74 ms 21936 KB Output is correct
9 Correct 99 ms 21932 KB Output is correct
10 Correct 81 ms 21936 KB Output is correct
11 Correct 82 ms 21968 KB Output is correct
12 Correct 82 ms 21940 KB Output is correct
13 Correct 80 ms 21960 KB Output is correct
14 Correct 72 ms 21936 KB Output is correct
15 Correct 80 ms 21940 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 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 44 ms 17840 KB Output is correct
9 Correct 47 ms 17840 KB Output is correct
10 Correct 53 ms 17916 KB Output is correct
11 Incorrect 46 ms 17840 KB Output isn't correct
12 Halted 0 ms 0 KB -