제출 #1245854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245854		khoi	Sirni (COCI17_sirni)	C++20	42 / 140	5093 ms	14304 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll  = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> P(n);
    for(int i = 0; i < n; i++){
        cin >> P[i];
    }

    // dist[v] = best known way to connect v into the tree
    const int INF = 1e9+7;
    vector<int> dist(n, INF);
    vector<char> in_mst(n, 0);

    // all unvisited nodes, sorted by P[v], so we can iterate them
    set<pii> rem;
    for(int i = 0; i < n; i++){
        rem.insert({ P[i], i });
    }

    // min‐heap of (best_dist, vertex)
    priority_queue< pii, vector<pii>, greater<pii> > pq;

    // Start from node 0
    dist[0] = 0;
    pq.push({0, 0});

    ll total = 0;
    int taken = 0;
    while(taken < n){
        auto [d,u] = pq.top(); 
        pq.pop();
        if(in_mst[u]) 
            continue;
        // add u into MST
        in_mst[u] = 1;
        total += d;
        taken++;

        // remove it from the “rem” set
        rem.erase({P[u], u});

        // now relax *all* remaining nodes v
        // we only push into the heap when we improve dist[v],
        // and since dist[v] only ever decreases, each v can be re‑pushed
        // O(log n) times at most ⇒ overall O(n log n).
        for(auto it = rem.begin(); it != rem.end(); ++it){
            int v = it->second;
            int w = min(P[u] % P[v], P[v] % P[u]);
            if(w < dist[v]){
                dist[v] = w;
                pq.push({w, v});
            }
        }
    }

    cout << total << "\n";
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14