| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1218511 | nguyenduydung109 | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int n;
vector<int> p, sz, minC0, minC1;
ll extra;
DSU(int _n, vector<ll>& C) : n(_n), p(n,-1), sz(n,1), minC0(n,LLONG_MAX), minC1(n,LLONG_MAX), extra(0) {
for(int i=0;i<n;i++){
p[i]=i;
if(i%2==0) minC0[i]=C[i];
else minC1[i]=C[i];
extra += C[i]; // mỗi nhóm 1 thành phần sẽ lẻ → cộng C[i]
}
}
int find(int x){ return p[x]==x ? x : p[x] = find(p[x]); }
void unite(int a, int b){
a = find(a); b = find(b);
if(a==b) return;
// remove old extra phí 2 nhóm
if(sz[a]%2) extra -= min(minC0[a], minC1[a]);
if(sz[b]%2) extra -= min(minC0[b], minC1[b]);
// merge nhỏ vào lớn
if(sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
minC0[a] = min(minC0[a], minC0[b]);
minC1[a] = min(minC1[a], minC1[b]);
// cộng extra mới nếu nhóm lẻ
if(sz[a]%2) extra += min(minC0[a], minC1[a]);
}
};
vector<ll> calculate_costs(vector<int>& W, vector<ll>& A, vector<ll>& B, vector<int>& E){
int N = W.size(), Q = E.size();
vector<ll> C(N);
ll S = 0;
for(int i=0;i<N;i++){
C[i] = A[i] - B[i];
S += B[i];
}
vector<int> idx(N);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j){ return W[i] < W[j]; });
vector<pair<ll, pair<int,int>>> edges;
for(int z=0;z<idx.size();z++){
int i = idx[z];
if(z+1 < N) edges.push_back({ llabs(W[idx[z+1]] - W[i]), {i, idx[z+1]} });
if(z+2 < N) edges.push_back({ llabs(W[idx[z+2]] - W[i]), {i, idx[z+2]} });
}
sort(edges.begin(), edges.end());
vector<pair<int,int>> Qs;
for(int i=0;i<Q;i++) Qs.push_back({E[i], i});
sort(Qs.begin(), Qs.end());
DSU dsu(N, C);
vector<ll> ans(Q);
int epos = 0;
for(auto& [limit, qi] : Qs){
while(epos < edges.size() && edges[epos].first <= limit){
dsu.unite(edges[epos].second.first, edges[epos].second.second);
epos++;
}
ans[qi] = S + dsu.extra;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N; cin >> N;
vector<int> W(N);
vector<ll> A(N), B(N);
for(int i=0;i<N;i++) cin >> W[i] >> A[i] >> B[i];
int Q; cin >> Q;
vector<int> E(Q);
for(int i=0;i<Q;i++) cin >> E[i];
auto R = calculate_costs(W,A,B,E);
for(ll x : R) cout << x << "\n";
return 0;
}