Submission #1170759

#TimeUsernameProblemLanguageResultExecution timeMemory
1170759Zakir060나일강 (IOI24_nile)C++20
Compilation error
0 ms0 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; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccOx8SEM.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPpLRpu.o:nile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccOx8SEM.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `calculate_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status