oj.uz

답안 #1052346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052346 2024-08-10T13:37:56 Z vjudge1 Sirni (COCI17_sirni) C++17
0 / 140
 602 ms 786432 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 300010
typedef tuple<int,int,int> tiii;

vector<int> adj[MAXN];
vector<int> nums;

typedef vector<int> vi;
class UnionFind {
private:
    vi p,rank;
public:
    UnionFind(int n) {
        p.assign(n,0); for (int i = 0; i < n; i++) p[i] = i;
        rank.assign(n,0);
    }

    int findSet(int i) {
        return (p[i] == i) ? i : (p[i] == findSet(p[i]));
    }

    bool isSameSet(int i, int j) {
        return (findSet(i) == findSet(j));
    }

    void unionSet(int i, int j) {
    int x = findSet(i), y = findSet(j);
    if (x == y) return;

    if (rank[x] > rank[y]) swap(x,y);
    p[x] = y;
    if (rank[x] == rank[y]) ++rank[y];
}


};




int main()
{

    int n; cin >> n;
    for (int i = 0; i< n; i++) {
        int a; cin >> a;
        nums.push_back(a);
    }
    vector<tiii> EL;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int minimo = min(nums[i]%nums[j], nums[j]%nums[i]);
            EL.push_back({minimo, i, j});
        }
    }
    sort(EL.begin(), EL.end());

    int mst_cost = 0, num_taken = 0;
    UnionFind UF(n);

    for (auto &[w, u, v] : EL) {
    if (UF.isSameSet(u,v)) continue;
    mst_cost += w;
    UF.unionSet(u,v);
    ++num_taken;
    if(num_taken == n-1) break;
    }
    cout << mst_cost << '\n';


    return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 19912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 602 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 546 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 396 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 400 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 377 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 372 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -