| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278631 | Bui_Quoc_Cuong | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n, q;
array <int, 3> a[maxn];
int lab[maxn];
long long val[maxn], max_val[maxn];
long long ans = 0;
int find (int x) {
return lab[x] < 0 ? x : lab[x] = find(lab[x]);
}
bool joint (int u, int v) {
int x = find(u), y = find(v);
if (x == y) return 0;
int sz_x = abs(lab[x]);
int sz_y = abs(lab[y]);
if (sz_x == 1) {
} else {
ans-= val[x];
if (sz_x & 1) {
ans+= max_val[x];
} else {
}
}
if (sz_y == 1) {
} else {
ans-= val[y];
if (sz_y & 1) {
ans+= max_val[y];
}
}
max_val[x] = max(max_val[x], max_val[y]);
val[x]+= val[y];
lab[x]+= lab[y];
lab[y] = x;
if (abs(lab[x]) & 1) {
ans-= max_val[x];
}
ans+= val[x];
return 1;
}
long long getAns (int D) {
for (int i = 1; i <= n; i++) {
lab[i] = - 1;
max_val[i] = a[i][2] - a[i][1];
val[i] = a[i][2] - a[i][1];
}
vector <array <int, 3>> sorted;
for (int i = 2; i <= n; i++) {
sorted.push_back({abs(a[i][0] - a[i - 1][0]), i - 1, i});
}
ans = 0;
for (int i = 1; i <= n; i++) ans+= a[i][1];
for (auto [w, u, v] : sorted) {
if (w <= D) {
joint (u, v);
}
}
return ans;
}
vector <long long> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
vector <long long> res;
n = W.size();
q = E.size();
for (int i = 1; i <= n; i++) {
a[i][0] = W[i - 1];
}
for (int i = 1; i <= n; i++) {
a[i][1] = A[i - 1];
}
for (int i = 1; i <= n; i++) {
a[i][2] = B[i - 1];
}
sort(a + 1, a + 1 + n);
for (auto d : E) {
res.push_back(getAns(d));
}
return res;
}