oj.uz

Submission #1113658

# Submission time Handle Problem Language Result Execution time Memory
1113658 2024-11-17T00:49:04 Z vincentbucourt1 Nile (IOI24_nile) C++17
38 / 100
 91 ms 21688 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<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});
    // 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});
      // 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 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 848 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15796 KB Output is correct
2 Correct 54 ms 15796 KB Output is correct
3 Correct 50 ms 15812 KB Output is correct
4 Incorrect 42 ms 15800 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 45 ms 15784 KB Output is correct
2 Correct 53 ms 15804 KB Output is correct
3 Correct 55 ms 15800 KB Output is correct
4 Correct 64 ms 15800 KB Output is correct
5 Correct 47 ms 15800 KB Output is correct
6 Correct 56 ms 17324 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 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 848 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 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 53 ms 15796 KB Output is correct
8 Correct 54 ms 15796 KB Output is correct
9 Correct 50 ms 15812 KB Output is correct
10 Incorrect 42 ms 15800 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 45 ms 15784 KB Output is correct
2 Correct 53 ms 15804 KB Output is correct
3 Correct 55 ms 15800 KB Output is correct
4 Correct 64 ms 15800 KB Output is correct
5 Correct 47 ms 15800 KB Output is correct
6 Correct 56 ms 17324 KB Output is correct
7 Correct 70 ms 21436 KB Output is correct
8 Correct 70 ms 21608 KB Output is correct
9 Correct 82 ms 21688 KB Output is correct
10 Correct 78 ms 21688 KB Output is correct
11 Correct 79 ms 21688 KB Output is correct
12 Correct 82 ms 21684 KB Output is correct
13 Correct 83 ms 21688 KB Output is correct
14 Correct 65 ms 21432 KB Output is correct
15 Correct 91 ms 21688 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 1 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 53 ms 15796 KB Output is correct
9 Correct 54 ms 15796 KB Output is correct
10 Correct 50 ms 15812 KB Output is correct
11 Incorrect 42 ms 15800 KB Output isn't correct
12 Halted 0 ms 0 KB -