oj.uz

Submission #1057635

# Submission time Handle Problem Language Result Execution time Memory
1057635 2024-08-14T02:11:39 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 2173 ms 545052 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(s) s.begin(), s.end()

const int ar = 1e7+2;
const ll mod = 1e9+7;
const int oo = 1e9;

int n, x, ma = 0;
vector <int> a;

#define set3 pair <int, int>

vector <set3> edge[ar];

int lab[ar];

int find_set(int v) {
    return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);
}

bool union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a != b) {
        if (lab[a] > lab[b]) swap(a, b);
        lab[a] += lab[b];
        lab[b] = a;
        return 1;
    }
    return 0;
}
bool check[ar];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "MODST"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    a.push_back(0);
    for(int i = 1; i <= n; ++i) {
        cin >> x;
        a.push_back(x);
        ma = max(ma, x);
    }
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
    n = a.size() - 1;

    for(int i = 1; i <= n; ++i) {
        lab[i] = -1;
        vector <int> ex;
        if(i < n) {
            check[i + 1] = 1;
            ex.push_back(i + 1),
            edge[a[i + 1] % a[i]].push_back({i, i + 1});
        }
        for(int j = a[i] * 2; j <= ma; j += a[i]) {
            int p = lower_bound(all(a), j) - a.begin();
            if(p <= n && !check[p])
                check[p] = 1, ex.push_back(p),
                edge[a[p] % a[i]].push_back({i, p});
        }
        for(auto x : ex) check[x] = 0;
    }

    ll res = 0;
    for(int i = 0; i <= ma; ++i) if(edge[i].size())
    for(auto &[u, v] : edge[i]) if(union_sets(u, v))
        res += i;
    cout << res;

    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 238800 KB Output is correct
2 Correct 67 ms 241408 KB Output is correct
3 Correct 44 ms 238936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 238932 KB Output is correct
2 Correct 337 ms 239416 KB Output is correct
3 Correct 44 ms 239124 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 238940 KB Output is correct
2 Correct 41 ms 238672 KB Output is correct
3 Correct 44 ms 238940 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 248884 KB Output is correct
2 Correct 292 ms 280472 KB Output is correct
3 Correct 146 ms 253880 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 240464 KB Output is correct
2 Correct 109 ms 261072 KB Output is correct
3 Correct 109 ms 248852 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 260868 KB Output is correct
2 Correct 382 ms 291536 KB Output is correct
3 Correct 141 ms 252136 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 242164 KB Output is correct
2 Correct 340 ms 285796 KB Output is correct
3 Correct 131 ms 251864 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 251316 KB Output is correct
2 Correct 1546 ms 459732 KB Output is correct
3 Correct 146 ms 253636 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 251744 KB Output is correct
2 Correct 2173 ms 545052 KB Output is correct
3 Correct 235 ms 257488 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 240988 KB Output is correct
2 Correct 1886 ms 533956 KB Output is correct
3 Correct 142 ms 253736 KB Output is correct