Submission #1245971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245971		khoi	Sirni (COCI17_sirni)	C++20	Compilation error	0 ms	0 KiB

sirni

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

// Một struct để đẩy vào min‐heap cạnh giữa hai đỉnh l < r
struct Edge {
    int l, r;
    int w;
    bool operator<(Edge const& o) const {
        return w > o.w; // để priority_queue mặc định thành min‐heap
    }
};

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];
    }
    // Nếu có giá trị trùng, chỉ giữ một
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    n = (int)P.size();
    
    // Khởi tạo multiset chứa cặp (value, original_index)
    set<pair<int,int>> S;
    S.reserve(n);
    for(int i = 0; i < n; i++){
        S.insert({P[i], i});
    }
    
    // Lưu iterator để tiện thao tác
    vector<set<pair<int,int>>::iterator> iter(n);
    {
        auto it = S.begin();
        while(it != S.end()){
            iter[it->second] = it;
            ++it;
        }
    }
    
    // Một mảng đánh dấu đã bị "xóa" (về mặt MST‐sweep)
    vector<bool> removed(n,false);
    
    // Min‐heap các cạnh giữa các phần tử kề nhau trong S
    priority_queue<Edge> pq;
    // Khởi tạo: với mỗi cặp kề nhau (it, nxt), thêm vào heap
    for(auto it = S.begin(); next(it) != S.end(); ++it){
        auto jt = next(it);
        int u_idx = it->second;
        int v_idx = jt->second;
        int w = jt->first % it->first;  // vì it->first < jt->first
        pq.push({u_idx, v_idx, w});
    }
    
    // Bắt đầu sweep: mỗi bước chọn cạnh nhỏ nhất nối hai phần tử đang còn trong S
    ll total = 0;
    while((int)S.size() > 1){
        auto E = pq.top(); pq.pop();
        int l = E.l, r = E.r, w = E.w;
        if(removed[l] || removed[r]) 
            continue;
        // kiểm tra thực sự l, r là kề nhau trong S
        auto itl = iter[l];
        auto nitr = next(itl);
        if(nitr == S.end() || nitr->second != r)
            continue;
        
        // Nối vào MST
        total += w;
        
        // “Xóa” r khỏi S
        auto itr = iter[r];
        auto prev_it = (itr == S.begin() ? S.end() : prev(itr));
        auto next_it = next(itr);
        removed[r] = true;
        S.erase(itr);
        
        // Nếu có hàng xóm mới (prev_it, next_it) thì đẩy cạnh giữa họ vào heap
        if(prev_it != S.end() && next_it != S.end()){
            int u2 = prev_it->second;
            int v2 = next_it->second;
            int w2 = next_it->first % prev_it->first;
            pq.push({u2, v2, w2});
        }
    }
    
    cout << total << "\n";
    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:31:7: error: 'class std::set<std::pair<int, int> >' has no member named 'reserve'
   31 |     S.reserve(n);
      |       ^~~~~~~