| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1170759 | Zakir060 | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/*
We will implement the "small-to-large" merging approach to maintain
the maximum weighted matching on a collection of disjoint paths.
Steps:
1) Sort artifacts by weight; keep track of original index.
2) Build edges between consecutive artifacts in sorted order:
- diff[i] = weight[i+1] - weight[i]
- saving[i] = (A[i] - B[i]) + (A[i+1] - B[i+1])
3) Sort these edges by diff ascending.
4) Sort queries by D ascending; process from smallest to largest.
5) Maintain a Union-Find structure plus, for each connected component,
a "path" of vertices in ascending order, and a DP array that yields
the maximum sum of these "savings" from pairing.
6) As we activate edges (in ascending diff), if they connect two different
components, we merge them (small-to-large) and recompute the DP for
the merged path in O(size_of_merged_path). Summation over merges
gives O(N log N).
7) After processing all edges with diff <= D_j, the sum over all
connected components' matchings is the maximum possible total saving.
Then the minimal transport cost = sum(A) - sum_of_all_matchings.
*/
static const bool DEBUG = false;
// A simple Union-Find to keep track of which vertices are in which component.
struct DSU {
int n;
vector<int> parent, size;
// We'll also store an ID or pointer to the "path data" for each root.
// pathID[root] = index in a separate structure that keeps the path's data.
vector<int> pathID;
DSU(int n) : n(n), parent(n), size(n,1), pathID(n) {
for(int i=0; i<n; i++){
parent[i] = i;
pathID[i] = i; // initially each node has its own path
}
}
int findp(int v){
while(parent[v] != v) {
parent[v] = parent[parent[v]];
v = parent[v];
}
return v;
}
bool unite(int a, int b){
a = findp(a);
b = findp(b);
if(a == b) return false;
// union by size
if(size[a] < size[b]) std::swap(a,b);
// attach b under a
parent[b] = a;
size[a] += size[b];
return true;
}
};
// We will store, for each connected component (root), a struct PathData
// containing:
// 1) A list of vertices in ascending order of their "position" along
// the sorted-artifacts axis. (We'll call them path[].)
// 2) A DP array dp[] so that dp[i] = maximum sum of "savings" we can get
// by pairing among the first i vertices of that path-list. We'll actually
// store dp of length path.size()+1, using typical 1D DP for maximum
// weighted matching on a path.
//
// The "weight of edge i->i+1" is s_i = Z[path[i]] + Z[path[i+1]],
// only if they are consecutive in the global sorted array. Because
// that's the boat-sharing condition.
struct PathData {
// The vertices in this connected component (in ascending order of their
// position along the sorted-artifacts line). We'll store their actual
// "sorted index" for reference, plus we can store Z[v] = (A[v] - B[v]) if we like.
vector<int> verts; // these are indices in [0..N-1] (the *sorted* positions)
vector<long long> dp; // dp[i] = best sum of savings using first i vertices in 'verts'
// We'll also keep an auxiliary array of the "edge savings" between consecutive
// vertices: s[i] = Z[verts[i]] + Z[verts[i+1]].
// The total maximum matching for this path is dp[verts.size()].
long long totalMatching = 0LL; // dp.back()
// We'll keep an array sEdges for i in [0..verts.size()-2].
// sEdges[i] = sum of (A-B) for verts[i] and verts[i+1].
vector<long long> sEdges;
PathData() { }
// Build a path with a single vertex => no edges => totalMatching=0
PathData(int singleV) {
verts.push_back(singleV);
dp.resize(2, 0LL); // dp[0]=0, dp[1]=0 => no edges
totalMatching=0LL;
}
// Recompute the DP from scratch once 'verts' is fully set in ascending order.
void buildDP(const vector<long long> &Z){
int L = (int)verts.size();
dp.assign(L+1, 0LL);
// build sEdges
sEdges.assign(L-1, 0LL);
for(int i=0; i+1<L; i++){
sEdges[i] = Z[ verts[i] ] + Z[ verts[i+1] ];
}
// standard O(L) DP for maximum weighted matching on a path
// dp[i+1] = max of dp[i], or dp[i-1] + sEdges[i-1] (if i>=1)
// but note that edge between i-1 and i is sEdges[i-1].
dp[0] = 0LL;
dp[1] = 0LL;
for(int i=2; i<=L; i++){
// i in [2..L], edge index = i-2 in sEdges
long long noPick = dp[i-1];
long long pick = dp[i-2] + sEdges[i-2];
dp[i] = max(noPick, pick);
}
totalMatching = dp[L];
}
};
// We'll keep a global structure that maintains a PathData for each root in DSU.
// On a "unite" operation, we do "small-to-large" merging of PathData.
struct PathManager {
// We store a vector<PathData> of size N initially (each single-vertex).
// However, not all entries remain "active": only the one pointed to by
// DSU::pathID[root] is the active path for that root.
vector<PathData> comp;
// We also store an array Z[v] = (A[v] - B[v]) for convenience.
vector<long long> Z;
// We'll store the total sum of matchings across all components,
// so that after each union we can update it quickly.
long long globalMatchingSum = 0LL;
PathManager() { }
PathManager(int n, const vector<long long>& zVals){
comp.resize(n);
Z = zVals;
// initialize each path with one vertex
for(int i=0; i<n; i++){
comp[i] = PathData(i); // single-vertex path
// globalMatchingSum remains 0 (since no edges in singletons)
}
}
// merges the path of "src" into the path of "dst"
// The new path is appended in ascending order of sorted-index.
// Then we rebuild DP in O(sz1 + sz2).
void mergePaths(int dstID, int srcID){
// We'll merge the smaller path into the bigger path
auto &D = comp[dstID];
auto &S = comp[srcID];
// Remove old matching sums from global
globalMatchingSum -= (D.totalMatching + S.totalMatching);
// We now merge the vertex-lists. We know they are each sorted by their
// "verts" (which represent sorted positions). We'll do a standard
// merge of two sorted lists:
vector<int> merged;
merged.reserve(D.verts.size() + S.verts.size());
int i=0, j=0;
while(i < (int)D.verts.size() && j < (int)S.verts.size()){
if(D.verts[i] < S.verts[j]) merged.push_back(D.verts[i++]);
else merged.push_back(S.verts[j++]);
}
while(i < (int)D.verts.size()) merged.push_back(D.verts[i++]);
while(j < (int)S.verts.size()) merged.push_back(S.verts[j++]);
D.verts.swap(merged);
// Rebuild DP in O(size_of_merged)
D.buildDP(Z);
// S is now unused; but we won't bother clearing it. It's enough that the DSU
// won't use srcID's path again for the root.
// Add the new matching sum
globalMatchingSum += D.totalMatching;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> W(N), A(N), B(N);
for(int i=0; i<N; i++){
cin >> W[i] >> A[i] >> B[i];
}
int Q;
cin >> Q;
vector<long long> E(Q);
for(int j=0; j<Q; j++){
cin >> E[j];
}
// 1) Sort artifacts by weight, keep track of original index
vector<int> idx(N);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b){
return W[a] < W[b];
});
// Precompute sumA = sum of all A[i].
long long sumA = 0LL;
for(int i=0; i<N; i++){
sumA += A[i];
}
// We'll define a "Z[v]" = (A[v] - B[v]) for convenience
// but we need them in the order of the "sorted positions".
// Actually, we will store Z for the original indexing (Z[v] = A[v]-B[v]),
// but remember that "consecutive in sorted order" means consecutive in 'idx'.
vector<long long> Z(N);
for(int i=0; i<N; i++){
Z[i] = (long long)A[i] - (long long)B[i];
}
// 2) Build edges between consecutive artifacts in sorted order:
// E[i]: connects sorted positions i and i+1, i in [0..N-2].
// diff[i] = W[idx[i+1]] - W[idx[i]]
// saving = Z[idx[i]] + Z[idx[i+1]]
struct Edge {
long long diff;
int u, v; // these are *sorted positions*, i and i+1
long long saving;
};
vector<Edge> edges;
edges.reserve(N-1);
for(int i=0; i+1<N; i++){
long long d = W[idx[i+1]] - W[idx[i]];
long long s = Z[idx[i]] + Z[idx[i+1]];
edges.push_back({d, i, i+1, s});
}
// sort edges by diff ascending
sort(edges.begin(), edges.end(), [&](auto &a, auto &b){
return a.diff < b.diff;
});
// We'll answer queries in ascending order of E[j].
// We'll keep track of (D_j, original_index_of_query).
vector<pair<long long,int>> queries(Q);
for(int j=0; j<Q; j++){
queries[j] = {E[j], j};
}
sort(queries.begin(), queries.end(), [&](auto &a, auto &b){
return a.first < b.first;
});
// 3) DSU on the "N" *vertices*, which here are the sorted positions 0..N-1.
// Each vertex i corresponds to idx[i] in the original set of artifacts.
// We'll also store a PathManager to maintain path-level data for each root.
DSU dsu(N);
// Initialize path manager with N single-vertex paths
// For path i, we store just "i" as the vertex. The "Z" array we pass is
// also of length N, but remember we want Z for the *artifact that sits
// in sorted position i*. That is Z[idx[i]]. So let's build a "Zsorted[i]"
// that corresponds to the artifact at sorted position i.
vector<long long> Zsorted(N);
for(int i=0; i<N; i++){
Zsorted[i] = Z[ idx[i] ];
}
PathManager pm(N, Zsorted);
// dsu.pathID[i] initially = i, meaning "component i is stored in pm.comp[i]".
// pm.comp[i] is a single-vertex path containing [i].
// We'll do a Kruskal-like sweep over edges in ascending order of diff,
// and also handle queries in ascending order of D_j.
long long currSumMatching = 0LL; // pm.globalMatchingSum
// Actually we keep that in pm.globalMatchingSum, so we won't store separately.
// We'll store answers in a vector:
vector<long long> ans(Q);
int ePtr = 0; // pointer over edges
for(auto &qq : queries){
long long limitD = qq.first;
int qidx = qq.second;
// Activate edges whose diff <= limitD
while(ePtr < (int)edges.size() && edges[ePtr].diff <= limitD){
// This edge is edges[ePtr]
int u = edges[ePtr].u; // sorted-position
int v = edges[ePtr].v;
int ru = dsu.findp(u);
int rv = dsu.findp(v);
if(ru != rv){
// unite them
bool ok = dsu.unite(ru, rv);
if(ok){
// After the union, the parent is dsu.findp(ru).
int nr = dsu.findp(u); // new root
int oldr = (nr == ru ? rv : ru);
// We want to merge the path data of oldr into nr,
// or vice versa, doing small-to-large.
int big = nr, small = oldr;
if(pm.comp[ dsu.pathID[ru] ].verts.size() <
pm.comp[ dsu.pathID[rv] ].verts.size()){
big = oldr;
small = nr;
}
// pathID[big] remains the path container,
// we merge pathID[small] into pathID[big].
int bigID = dsu.pathID[big];
int smallID = dsu.pathID[small];
pm.mergePaths(bigID, smallID);
// Now we must tell DSU that the root's pathID is bigID
dsu.pathID[nr] = bigID;
dsu.pathID[oldr] = bigID;
}
}
ePtr++;
}
// Now pm.globalMatchingSum is the maximum total saving across all comps
long long totalSaving = pm.globalMatchingSum;
long long cost = sumA - totalSaving;
ans[qidx] = cost;
}
// We printed answers in sorted order of queries, so reorder them
// Actually, we built queries as (E[j], j), then sorted by E[j].
// We have stored the result in ans[qidx]. That's correct.
// We just need to output them in the original order j = 0..Q-1.
// The array ans[] is already in the correct index because we used qidx
// as the position in ans. So just output ans[0], ans[1], ... in that order
// **but** we must watch out: we used queries[j] = { E[j], j }, and then sorted by
// the first. So the final "ans[qidx]" holds the cost for query #qidx.
// It's already correct to just print in ascending qidx from 0..Q-1:
for(int j=0; j<Q; j++){
cout << ans[j] << "\n";
}
return 0;
}