oj.uz

Submission #1057624

# Submission time Handle Problem Language Result Execution time Memory
1057624 2024-08-14T01:50:24 Z vjudge1 Sirni (COCI17_sirni) C++17
84 / 140
 1410 ms 786432 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define task "test"

using namespace std;

using i64 = int64_t;

struct edge
{
    int u, v, w;
    edge (int _u, int _v, int _w) : u(_u), v(_v), w(_w) {};
};

const int N = 1e5+5;

struct DSU
{
    int p[N];

    DSU (int n)
    {
        for(int i  = 1; i <= n; ++i) p[i] = i;
    }

    int find(int a)
    {
        return (a == p[a]) ? a : p[a] = find(p[a]);
    }

    void unite(int a, int b)
    {
        a = find(a); b = find(b);
        if(a != b)
        {
            p[b] = a;
        }
    }
};

int n, nxt[N];
vector <int> a;
vector <edge> g;

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    a.resize(n);
    for(auto &i:a) cin >> i;

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    for(int i = 0; i < (int)a.size(); ++i)
    {
        int l = lower_bound(a.begin(), a.end(), a[i]) - a.begin();
        for(int j = a[i]; j <= *prev(a.end()); j += a[i])
        {
            g.emplace_back(i, l, a[l] % a[i]);
            int r = lower_bound(a.begin(), a.end(), j+a[i]) - a.begin();
            nxt[l]++; nxt[r]--;
            l = r;
        }
    }

    for(int i = 0; i < (int)a.size() - 1; ++i)
    {
        if(i > 0) nxt[i] += nxt[i-1];
        if(nxt[i] > 0) g.emplace_back(i, i+1, a[i+1] % a[i]);
    }

    sort(g.begin(), g.end(), [](edge c, edge d) {return c.w < d.w;});

    DSU dsu(n);

    i64 ans = 0;
    for(edge e:g)
    {
        if(dsu.find(e.u) != dsu.find(e.v))
        {
            dsu.unite(e.u, e.v);
            ans += e.w;
        }
    }

    cout << ans;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 114 ms 50352 KB Output is correct
3 Correct 3 ms 1304 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Runtime error 391 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 27704 KB Output is correct
2 Correct 395 ms 100412 KB Output is correct
3 Correct 173 ms 50980 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4048 KB Output is correct
2 Correct 155 ms 50644 KB Output is correct
3 Correct 110 ms 26768 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 52652 KB Output is correct
2 Correct 543 ms 100520 KB Output is correct
3 Correct 153 ms 27092 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8540 KB Output is correct
2 Correct 478 ms 100516 KB Output is correct
3 Correct 168 ms 52392 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 27616 KB Output is correct
2 Runtime error 1032 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 27576 KB Output is correct
2 Runtime error 909 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5580 KB Output is correct
2 Runtime error 1410 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -