Submission #1151425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151425		ainta	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1349 ms	31652 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
using namespace std;
typedef long long ll;

// ----- Edge structure -----
struct Edge {
    int u, v;
    ll w;
    int id; // original id (0-indexed)
};

// ----- Global Variables -----
int N, M;
vector<Edge> edges; // original edges
// We'll compute Lbound and Rbound for each edge (indexed by its original id)
vector<ll> Lbound, Rbound;
 
// ----- DFS in Tree T -----
// T is maintained as an adjacency list: for each node, a list of (neighbor, edge id)
bool dfsPath(int cur, int target, int parent, vector<int> &path) {
    if(cur == target) return true;
    for(auto &p : path); // dummy
    // We'll pass T as a global reference below.
    return false;
}
 
// We'll write a DFS that finds the unique path from 's' to 't' in tree T.
// It stores in 'path' the edge ids (from T) on the path.
bool findPath(int cur, int target, int parent, const vector<vector<pair<int,int>>>& T, vector<int> &path) {
    if(cur == target) return true;
    for(auto &pr : T[cur]) {
        int nxt = pr.first, edgeId = pr.second;
        if(nxt == parent) continue;
        if(findPath(nxt, target, cur, T, path)) {
            path.push_back(edgeId);
            return true;
        }
    }
    return false;
}
 
// ----- Lower Bound Computation -----
// Process edges in increasing order. Maintain tree T as an undirected spanning tree (as an adjacency list).
// For each edge (in sorted order) with endpoints u and v:
//   - If u and v are not connected in T (found by DFS), then set Lbound = 1 and add the edge into T.
//   - Otherwise, find the unique path in T between u and v, let j be the edge on that path with maximum weight.
//     Then set Lbound = (w_i + w_j) / 2 + 1.
//     Also, if w_i < w_j, then remove edge j from T and add edge i.
void computeLowerBounds() {
    Lbound.assign(M, 0);
    // T: tree maintained as adjacency list; T[node] = vector of (neighbor, edge id)
    vector<vector<pair<int,int>>> T(N);
    
    // Sort edges in increasing order by weight.
    vector<Edge> sorted = edges;
    sort(sorted.begin(), sorted.end(), [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    
    // For connectivity checking we use DFS in T.
    auto connected = [&](int s, int t) -> bool {
        vector<bool> vis(N, false);
        function<bool(int)> dfs = [&](int cur) -> bool {
            if(cur == t) return true;
            vis[cur] = true;
            for(auto &pr : T[cur]) {
                int nxt = pr.first;
                if(!vis[nxt] && dfs(nxt))
                    return true;
            }
            return false;
        };
        return dfs(s);
    };
    
    // For each edge in sorted order, process it.
    for(auto &e : sorted) {
        int u = e.u, v = e.v;
        if(!connected(u, v)) {
            // Not connected: edge e is critical for small X.
            Lbound[e.id] = 0;
            // Add e to T:
            T[u].push_back({v, e.id});
            T[v].push_back({u, e.id});
        } else {
            // u and v are already connected in T.
            // Find the unique path from u to v in T.
            vector<int> pathEdgeIds;
            findPath(u, v, -1, T, pathEdgeIds);
            // The path is stored in reverse order; we scan all edge ids in the path.
            int maxEdgeId = -1;
            ll minW = 1e18;
            for (int id : pathEdgeIds) {
                ll wtemp = edges[id].w; // original weight of that edge.
                if(wtemp < minW) { minW = wtemp; maxEdgeId = id; }
            }
            // Compute lower bound for current edge:
            // According to the idea: L_val = (w_i + w_j) / 2 + 1.
            Lbound[e.id] = (e.w + minW) / 2 + 1;
            // Additionally, if current edge is strictly lighter than the one on the path,
            // then we can replace that heavier edge in T with the current edge.
                // Remove edge maxEdgeId from T.
                int a = edges[maxEdgeId].u, b = edges[maxEdgeId].v;
                auto removeEdge = [&](int x, int y, int eid) {
                    for(auto it = T[x].begin(); it != T[x].end(); ++it) {
                        if(it->first == y && it->second == eid) {
                            T[x].erase(it);
                            break;
                        }
                    }
                };
                removeEdge(a, b, maxEdgeId);
                removeEdge(b, a, maxEdgeId);
                // Add current edge e instead.
                T[u].push_back({v, e.id});
                T[v].push_back({u, e.id});
        }
    }
}
 
// ----- Upper Bound Computation -----
// Process edges in decreasing order. We use a similar procedure, maintaining a spanning tree T.
// For each edge (in descending order) with endpoints u and v:
//   - If not connected in T, then Rbound = 10^9.
//   - Otherwise, find the unique path and let k be the edge with maximum weight on the path.
//     Set Rbound = (w_i + w_k) / 2.
//     Also, if w_i < w_k, then replace that edge in T by the current edge.
void computeUpperBounds() {
    Rbound.assign(M, 0);
    vector<vector<pair<int,int>>> T(N);
    
    vector<Edge> sorted = edges;
    sort(sorted.begin(), sorted.end(), [](const Edge &a, const Edge &b){
        return a.w > b.w; // descending order.
    });
    
    auto connected = [&](int s, int t) -> bool {
        vector<bool> vis(N, false);
        function<bool(int)> dfs = [&](int cur) -> bool {
            if(cur == t) return true;
            vis[cur] = true;
            for(auto &pr : T[cur]) {
                int nxt = pr.first;
                if(!vis[nxt] && dfs(nxt))
                    return true;
            }
            return false;
        };
        return dfs(s);
    };
    
    for(auto &e : sorted) {
        int u = e.u, v = e.v;
        if(!connected(u, v)) {
            // Not connected: edge is used for very large X.
            Rbound[e.id] = 1000000001LL;
            T[u].push_back({v, e.id});
            T[v].push_back({u, e.id});
        } else {
            vector<int> pathEdgeIds;
            findPath(u, v, -1, T, pathEdgeIds);
            int maxEdgeId = -1;
            ll maxW = -1;
            for (int id : pathEdgeIds) {
                ll wtemp = edges[id].w;
                if(wtemp > maxW) { maxW = wtemp; maxEdgeId = id; }
            }
            Rbound[e.id] = (e.w + maxW) / 2; // note: floor division.
                int a = edges[maxEdgeId].u, b = edges[maxEdgeId].v;
                auto removeEdge = [&](int x, int y, int eid) {
                    for(auto it = T[x].begin(); it != T[x].end(); ++it) {
                        if(it->first == y && it->second == eid) {
                            T[x].erase(it);
                            break;
                        }
                    }
                };
                removeEdge(a, b, maxEdgeId);
                removeEdge(b, a, maxEdgeId);
                T[u].push_back({v, e.id});
                T[v].push_back({u, e.id});
        }
    }
}
 
// ----- Main -----
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> M;
    edges.resize(M);
    for (int i = 0; i < M; i++){
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--; // convert to 0-indexed
        edges[i] = {u, v, w, i};
    }
    Lbound.resize(M); Rbound.resize(M);
    computeLowerBounds();
    computeUpperBounds();
 
    // (For debugging, you may print each edge's interval:)
    // for (int i = 0; i < M; i++){
    //     cout << "Edge " << i+1 << " (w=" << edges[i].w << "): [" << Lbound[i] << ", " << Rbound[i] << "]\n";
    // }
 
    // Answer queries.
    // For each query X, the MST chosen is exactly the set of edges i for which X is in [Lbound[i], Rbound[i]].
    // The cost is sum_{i with X in [L_i,R_i]} |w_i - X|.
    int Q; cin >> Q;

    vector<pli> AA, BB;
    for(int i=0;i<M;i++){
        AA.pb({Lbound[i],-1});
        AA.pb({edges[i].w+1,2});
        AA.pb({Rbound[i]+1,-1});
        BB.pb({Lbound[i],edges[i].w});
        BB.pb({edges[i].w+1,-2*edges[i].w});
        BB.pb({Rbound[i]+1,edges[i].w});
    }
    sort(all(AA));
    sort(all(BB));
    vc<ll>SA(si(AA)), SB(si(AA));
    rep(i,si(AA)){
        SA[i] = AA[i].se;
        SB[i] = BB[i].se;
        if(i) SA[i]+=SA[i-1], SB[i]+=SB[i-1];
    }
    while(Q--){
        ll X; cin >> X;
        ll totalCost = 0;
        int pv = lower_bound(all(AA),pli(X+1,-5)) - AA.begin(); pv--;
        cout << SA[pv] * X + SB[pv] << "\n";
    }
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23