제출 #1057624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057624		vjudge1	Sirni (COCI17_sirni)	C++17	84 / 140	1410 ms	786432 KiB

sirni

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14