oj.uz

Submission #881851

# Submission time Handle Problem Language Result Execution time Memory
881851 2023-12-02T04:56:24 Z boyliguanhan Sirni (COCI17_sirni) C++17
0 / 140
 5000 ms 259684 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
int nxt[10001000], p[100100],pa[100100],n,mx,ans;
set<tuple<int,int,int>> edges;
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,p[i]),nxt[p[i]]=i;
    for(int i = mx; i--;)
        if(!nxt[i])
            nxt[i]=nxt[i+1];
    for(int i = 1; i <= n; i++)
        for(int j = 2*p[i]; j <= mx; j++)
            if(nxt[j])
                edges.insert({p[nxt[j]]%p[i],i,nxt[j]});
            else break;
    for(auto [w,u,v]: edges) {
        if(w>mx/2)
            break;
        if(un(u,v))
            ans+=w;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5095 ms 42380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 17224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5051 ms 42348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5039 ms 237244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 120752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 259684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 247448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5081 ms 103180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5014 ms 124284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5017 ms 68172 KB Time limit exceeded
2 Halted 0 ms 0 KB -