oj.uz

답안 #1057626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057626 2024-08-14T01:52:47 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 672 ms 622096 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const int amax = 1e7;
int n, a[nmax], mx = 0;
vector <bool> vs;
vector <int> nxt, pos;
vector <vector <pii>> adj;
struct disjoint
{
    int root[nmax], sz[nmax];
    void init(int _sz)
    {
        iota(root + 1, root + _sz + 1, 1);
        memset(sz, 1, (_sz + 1) * sizeof(int));
    }
    int findset(int u)
    {
        if (root[u] == u) return u;
        return root[u] = findset(root[u]);
    }
    bool merge(int u, int v)
    {
        if ((u = findset(u)) == (v = findset(v))) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        root[v] = u;
        return 1;
    }
} dsu;
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    vs.resize(mx + 1);
    adj.resize(mx + 1);
    nxt.resize(mx + 2);
    pos.resize(mx + 2);
    dsu.init(n);
    for (int i = 1; i <= n; ++i)
    {
        nxt[a[i]] = a[i];
        if (!pos[a[i]]) pos[a[i]] = i;
    }
    for (int i = mx - 1; i >= 1; --i)
        if (!nxt[i])
            nxt[i] = nxt[i + 1];
    for (int i = 1; i <= n; ++i)
    {
        if (vs[a[i]]) continue;
        vs[a[i]] = 1;
        if (nxt[a[i] + 1])
            if ((a[i] << 1) > mx || nxt[a[i] << 1] != nxt[a[i] + 1])
                adj[nxt[a[i] + 1] - a[i]].eb(i, pos[nxt[a[i] + 1]]);
        for (int j = (a[i] << 1); j <= mx && nxt[j]; j += a[i])
            if (j + a[i] > mx || nxt[j + a[i]] != nxt[j])
                adj[nxt[j] - j].eb(i, pos[nxt[j]]);
    }
    ll ans = 0;
    for (int weight = 0; weight < mx; ++weight)
        for (auto &[u, v] : adj[weight])
            if (dsu.merge(u, v)) ans += weight;
    cout << ans;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:9:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:45:31: note: in expansion of macro 'nx'
   45 |     if (ifstream(task".inp")) nx
      |                               ^~
sirni.cpp:9:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:45:31: note: in expansion of macro 'nx'
   45 |     if (ifstream(task".inp")) nx
      |                               ^~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 314704 KB Output is correct
2 Correct 68 ms 315988 KB Output is correct
3 Correct 55 ms 313800 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 172 ms 314920 KB Output is correct
3 Correct 56 ms 314708 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 314644 KB Output is correct
2 Correct 55 ms 314204 KB Output is correct
3 Correct 56 ms 314708 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 42516 KB Output is correct
2 Correct 63 ms 71424 KB Output is correct
3 Correct 35 ms 47388 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 33628 KB Output is correct
2 Correct 39 ms 55132 KB Output is correct
3 Correct 30 ms 26788 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 54116 KB Output is correct
2 Correct 76 ms 85936 KB Output is correct
3 Correct 34 ms 45856 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10416 KB Output is correct
2 Correct 76 ms 80580 KB Output is correct
3 Correct 33 ms 44352 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 328272 KB Output is correct
2 Correct 497 ms 547068 KB Output is correct
3 Correct 98 ms 330836 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 327584 KB Output is correct
2 Correct 628 ms 622096 KB Output is correct
3 Correct 109 ms 334920 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 317276 KB Output is correct
2 Correct 672 ms 618740 KB Output is correct
3 Correct 35 ms 47108 KB Output is correct