oj.uz

답안 #882252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882252 2023-12-02T20:49:27 Z boyliguanhan Sirni (COCI17_sirni) C++17
140 / 140
 785 ms 521392 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define N 10000001
int nxt[N], p[100100],pa[N],vis[N],n,mx,ans;
vector<pair<int,int>> edges[N];
int abp(int n) {
    return (pa[n]?pa[n]=abp(pa[n]):n);
}
bool un(int a, int b) {
    a=abp(a);
    b=abp(b);
    if(a==b)
        return 0;
    pa[a]=b;
    return 1;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i], mx=max(mx,nxt[p[i]]=p[i]);
    for(int i = mx; i--;)
        if(!nxt[i])
            nxt[i]=nxt[i+1];
    for(int i = 1; i <= mx; i++)
        if(nxt[i]==i&&(vis[i]^(vis[i]=1)))
            for(int j = i; j <= mx; vis[j]=1,j+=i){
                if(nxt[j]==j)
                    edges[0].push_back({i,j});
                if(nxt[j+1])
                    edges[nxt[j+1]%i].push_back({i,nxt[j+1]});
            }
    for(int i = 0; i<=5e6; i++)
        for(auto [u,v]: edges[i])
            if(un(u,v))
                ans+=i;
    cout << ans << '\n';
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:28:38: warning: operation on 'vis[i]' may be undefined [-Wsequence-point]
   28 |         if(nxt[i]==i&&(vis[i]^(vis[i]=1)))
      |                               ~~~~~~~^~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 294488 KB Output is correct
2 Correct 237 ms 344660 KB Output is correct
3 Correct 138 ms 314876 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 235272 KB Output is correct
2 Correct 511 ms 463024 KB Output is correct
3 Correct 157 ms 318280 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 295764 KB Output is correct
2 Correct 128 ms 284456 KB Output is correct
3 Correct 136 ms 304720 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 256120 KB Output is correct
2 Correct 136 ms 264476 KB Output is correct
3 Correct 131 ms 267320 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 249112 KB Output is correct
2 Correct 119 ms 260436 KB Output is correct
3 Correct 114 ms 249316 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 260724 KB Output is correct
2 Correct 149 ms 267472 KB Output is correct
3 Correct 116 ms 260472 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 240384 KB Output is correct
2 Correct 132 ms 266872 KB Output is correct
3 Correct 125 ms 266116 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 366732 KB Output is correct
2 Correct 620 ms 489804 KB Output is correct
3 Correct 252 ms 369788 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 370312 KB Output is correct
2 Correct 728 ms 521392 KB Output is correct
3 Correct 371 ms 423088 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 350264 KB Output is correct
2 Correct 785 ms 484804 KB Output is correct
3 Correct 128 ms 268088 KB Output is correct