oj.uz

Submission #470851

# Submission time Handle Problem Language Result Execution time Memory
470851 2021-09-06T01:20:42 Z SirCovidThe19th Sirni (COCI17_sirni) C++17
140 / 140
 3909 ms 575044 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mN = 1e5 + 5, mP = 1e7 + 5;

int n, mx, ub[mP], par[mN], sz[mN]; long long ans; vector<int> A; vector<pair<int, int>> edg[mP];

int get(int i){
    return (i == par[i]) ? i : par[i] = get(par[i]);
}
void merge(int a, int b, int w){
    a = get(a); b = get(b); if (a == b) return;
    if (a > b) swap(a, b);
    par[a] = b; sz[b] += sz[a]; ans += w;
}

int main(){
    cin >> n; A.resize(n);
    for (int &i : A) cin >> i;
    sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end());
    n = A.size(); mx = A.back(); iota(par, par + n, 0); fill(sz, sz + n, 1);

    for (int i = 0; i < n; i++) ub[A[i]] = i;
    for (int i = mx, cur = n - 1; i >= 0; i--) (ub[i]) ? cur = ub[i] : ub[i] = cur;
    
    for (int i = 0; i < n - 1; i++)
        for (int x = A[i]; x <= mx; x += A[i]){
            int j = ub[x + (x == A[i])];
            if (A[j] < x + A[i])
                edg[A[j] % x].push_back({i, j});
        }
        
    for (int i = 0; i < mx; i++)
        for (auto edge : edg[i])
            merge(edge.first, edge.second, i);
    cout<<ans<<endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 274372 KB Output is correct
2 Correct 219 ms 276592 KB Output is correct
3 Correct 174 ms 274372 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235280 KB Output is correct
2 Correct 479 ms 274896 KB Output is correct
3 Correct 174 ms 274500 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 274372 KB Output is correct
2 Correct 180 ms 274132 KB Output is correct
3 Correct 177 ms 274552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 249592 KB Output is correct
2 Correct 341 ms 276924 KB Output is correct
3 Correct 241 ms 254772 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 240824 KB Output is correct
2 Correct 287 ms 261356 KB Output is correct
3 Correct 213 ms 247776 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 261596 KB Output is correct
2 Correct 397 ms 291744 KB Output is correct
3 Correct 237 ms 253408 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 239480 KB Output is correct
2 Correct 380 ms 285836 KB Output is correct
3 Correct 230 ms 252860 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 287296 KB Output is correct
2 Correct 1716 ms 484228 KB Output is correct
3 Correct 369 ms 289860 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 287288 KB Output is correct
2 Correct 3493 ms 575044 KB Output is correct
3 Correct 412 ms 294472 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 276636 KB Output is correct
2 Correct 3909 ms 569580 KB Output is correct
3 Correct 249 ms 254900 KB Output is correct