Submission #1278903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278903		chatgpt.orz	Cities (BOI16_cities)	C++20	0 / 100	78 ms	13696 KiB

cities

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n;
    vector<int> p, r;
    DSU(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        p.resize(n+1);
        r.assign(n+1,0);
        for(int i=1;i<=n;i++) p[i]=i;
    }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a = find(a); b = find(b);
        if(a==b) return false;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    if(!(cin >> n >> k >> m)) return 0;
    vector<int> special(k);
    vector<char> is_special(n+1, 0);
    for(int i=0;i<k;i++){
        cin >> special[i];
        is_special[special[i]] = 1;
    }

    struct Edge { int u,v; long long w; };
    vector<Edge> edges;
    edges.reserve(m);
    for(int i=0;i<m;i++){
        int u,v; long long w;
        cin >> u >> v >> w;
        edges.push_back({u,v,w});
    }

    // Kruskal: build MST adjacency
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){ return a.w < b.w; });
    DSU dsu(n);
    dsu.init(n);
    vector<vector<pair<int,long long>>> adj(n+1);
    int taken = 0;
    for(auto &e : edges){
        if(dsu.unite(e.u, e.v)){
            adj[e.u].push_back({e.v, e.w});
            adj[e.v].push_back({e.u, e.w});
            taken++;
            if(taken == n-1) break;
        }
    }

    if(k <= 1){
        cout << 0 << '\n';
        return 0;
    }

    // Root the tree at any special node (take special[0])
    int root = special[0];

    vector<int> parent(n+1, -1);
    vector<long long> pedge(n+1, 0); // weight of edge to parent
    vector<int> order; order.reserve(n);
    // iterative stack DFS to build parent+order (postorder)
    stack<int> st;
    st.push(root);
    parent[root] = 0; // mark visited, parent 0
    while(!st.empty()){
        int u = st.top(); st.pop();
        order.push_back(u);
        for(auto [v,w] : adj[u]){
            if(parent[v] == -1){
                parent[v] = u;
                pedge[v] = w;
                st.push(v);
            }
        }
    }
    // order currently is preorder (stack-based), we need postorder -> reverse it
    reverse(order.begin(), order.end());

    // cnt[u] = number of special nodes in subtree u
    vector<int> cnt(n+1, 0);
    for(int i=1;i<=n;i++) if(is_special[i]) cnt[i]=1;
    long long ans = 0;
    for(int u : order){
        if(u == root) continue;
        // u has parent parent[u], edge weight pedge[u]
        if(cnt[u] > 0 && cnt[u] < k){
            // this edge is necessary to connect specials on both sides
            ans += pedge[u];
        }
        // push counts up
        cnt[parent[u]] += cnt[u];
    }

    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26