oj.uz

답안 #948757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948757 2024-03-18T13:12:17 Z May27_th Sirni (COCI17_sirni) C++17
84 / 140
 907 ms 786436 KB 
#include<bits/stdc++.h>
#define taskname "a"
using namespace std;

void World_Final();
void Solve();

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen(taskname".in", "r")) {
        freopen(taskname".in", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    World_Final();
}

void World_Final(){
    int Tests = 1;
    //cin >> Tests;
    for (int i = 1; i <= Tests; i ++) {
        //cout << i << "\n";
        Solve();
    }
}

struct DSU{
    private:
        vector<int> par, sz;
    public:
        int ccp;
        DSU(int N) : par(N + 5), sz(N + 5) {
            ccp = N;
            for (int i = 1; i <= N; i ++) {
                par[i] = i;
                sz[i] = 1;
            }
        }
        /*void init(int N) {
            par.resize(N + 5); sz.resize(N + 5);
            for (int i = 1; i <= N; i ++) {
                par[i] = i; sz[i] = 1;
            }
        }*/

        int findPar(int u) {
            return (u == par[u] ? u : par[u] = findPar(par[u]));
        }

        //int getSize(int u) { return sz[findPar(u)]; }
        bool same(int u, int v) {
            return findPar(u) == findPar(v);
        }

        bool unite(int u, int v) {
            int paru = findPar(u);
            int parv = findPar(v);
            if (paru == parv) return false;
            if (sz[paru] < sz[parv]) swap(paru, parv);
            sz[paru] += sz[parv];
            par[parv] = paru;

            return true;
        }

};

const int MAXN = 1e5 + 10;
const int64_t INF = 1e18;

struct Edge{
    int u, v, c;
};
void Solve(){
    int N; cin >> N;
    vector<Edge> ve;
    vector<int> P(N);
    for (auto &x : P) cin >> x;
    sort (P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    N = P.size();
    vector<int> pos(P.back() + 4, -1);
    for (int i = 0; i < N; i ++) {
        pos[P[i]] = i;
    }
    for (int i = P.back() - 1; i >= 0; i --) {
        if (pos[i] == -1) {
            pos[i] = pos[i + 1];
        }
    }
    for (int i = 0; i < N; i ++) {
        if (i < N - 1) {
            ve.push_back({i, i + 1, min(P[i], P[i + 1] % P[i])});
        }
        for (int j = 2 * P[i]; j <= P.back(); j += P[i]) {
            ve.push_back({i, pos[j], min(P[pos[j]] % P[i], P[i])});
        }
    } sort (ve.begin(), ve.end(), [&] (Edge &a, Edge &b){
        return a.c < b.c;
    });
    int64_t ans = 0; DSU d(N + 10);
    for (auto [u, v, c] : ve) {
        if (d.unite(u, v)) {
            ans += c;
        }
    } cout << ans;


}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(taskname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 39512 KB Output is correct
2 Correct 163 ms 90284 KB Output is correct
3 Correct 30 ms 39960 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 754 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 39516 KB Output is correct
2 Correct 27 ms 39516 KB Output is correct
3 Correct 29 ms 39836 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 30664 KB Output is correct
2 Correct 218 ms 54540 KB Output is correct
3 Correct 118 ms 55972 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 7632 KB Output is correct
2 Correct 166 ms 54520 KB Output is correct
3 Correct 71 ms 28096 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 55216 KB Output is correct
2 Correct 294 ms 104360 KB Output is correct
3 Correct 105 ms 31176 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 9168 KB Output is correct
2 Correct 337 ms 105288 KB Output is correct
3 Correct 106 ms 29376 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 64960 KB Output is correct
2 Runtime error 701 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 65908 KB Output is correct
2 Runtime error 702 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 42900 KB Output is correct
2 Runtime error 907 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -