oj.uz

답안 #1110898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110898 2024-11-10T23:43:46 Z vincentbucourt1 나일강 (IOI24_nile) C++17
0 / 100
 61 ms 30392 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 15040 KB Output is correct
2 Correct 40 ms 15040 KB Output is correct
3 Correct 40 ms 15032 KB Output is correct
4 Incorrect 41 ms 15192 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 15040 KB Output is correct
2 Correct 43 ms 15032 KB Output is correct
3 Correct 50 ms 15036 KB Output is correct
4 Correct 53 ms 14988 KB Output is correct
5 Runtime error 61 ms 30392 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 15040 KB Output is correct
2 Correct 43 ms 15032 KB Output is correct
3 Correct 50 ms 15036 KB Output is correct
4 Correct 53 ms 14988 KB Output is correct
5 Runtime error 61 ms 30392 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 2 ms 1104 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -