oj.uz

답안 #1113659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113659 2024-11-17T00:58:43 Z vincentbucourt1 나일강 (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

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -