| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1232540 | nibert | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "nile.h"
using namespace std;
struct DSU {
vector<int> parent;
DSU(int n) : parent(n, -1) {}
int find(int x) {
if (parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (parent[x] > parent[y]) swap(x, y);
parent[x] += parent[y];
parent[y] = x;
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
// 1. Create sorted order of weights (index-based)
vector<int> ordW(N);
iota(ordW.begin(), ordW.end(), 0);
sort(ordW.begin(), ordW.end(), [&](int i, int j) {
return W[i] < W[j];
});
// 2. Create edges between nearby elements in sorted weight order
vector<array<int, 3>> edges;
for (int i = 0; i + 1 < N; ++i) {
int u = ordW[i];
int v = ordW[i + 1];
edges.push_back({abs(W[u] - W[v]), u, v});
}
for (int i = 0; i + 2 < N; ++i) {
int u = ordW[i];
int v = ordW[i + 2];
edges.push_back({abs(W[u] - W[v]), u, v});
}
sort(edges.begin(), edges.end());
// 3. Offline sort of queries
vector<int> ordE(Q);
iota(ordE.begin(), ordE.end(), 0);
sort(ordE.begin(), ordE.end(), [&](int i, int j) {
return E[i] < E[j];
});
vector<long long> res(Q);
DSU dsu(N);
// 4. Start with total cost = all artifacts alone (A[i])
long long total = accumulate(A.begin(), A.end(), 0LL);
// 5. Mark each artifact as active and store current cost mode (A[i] used or B[i] used)
vector<bool> used(N, false);
int ei = 0;
for (int qi = 0; qi < Q; ++qi) {
int d = E[ordE[qi]];
while (ei < edges.size() && edges[ei][0] <= d) {
int u = edges[ei][1];
int v = edges[ei][2];
int ru = dsu.find(u);
int rv = dsu.find(v);
if (ru != rv) {
// remove solo cost
total -= A[ru] == -1 ? 0 : A[ru];
total -= A[rv] == -1 ? 0 : A[rv];
// unite sets
dsu.unite(u, v);
int newRoot = dsu.find(u);
// compute best upgrade for new set
long long newCost = 0;
vector<int> group;
for (int i = 0; i < N; ++i)
if (dsu.find(i) == newRoot)
group.push_back(i);
if (group.size() % 2 == 0) {
for (int i : group)
newCost += B[i];
} else {
long long extra = LLONG_MAX;
for (int i : group)
newCost += B[i], extra = min(extra, A[i] - B[i]);
newCost += extra;
}
// update total
total += newCost;
// mark A for root as -1 to prevent double-subtraction
A[newRoot] = -1;
}
++ei;
}
res[ordE[qi]] = total;
}
return res;
}