oj.uz

Submission #637010

# Submission time Handle Problem Language Result Execution time Memory
637010 2022-08-31T05:42:24 Z nguyen31hoang08minh2003 Sirni (COCI17_sirni) C++14
140 / 140
 1427 ms 638396 KB 
/*
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
 //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\
//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\
\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //
 \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\
=/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\=
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
 //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\
//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\
\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //
 \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\
=/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\=
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

struct DisjointSet {
private:
    mutable std::vector<int> r;
public:
    DisjointSet() {};
    DisjointSet(const int n): r(n, -1) {};

    void reload() {
        std::fill(r.begin(), r.end(), -1);
    };

    int getRoot(const int x) const {
        return r[x] < 0 ? x : (r[x] = getRoot(r[x]));
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (r[x] > r[y])
            std::swap(x, y);
        r[x] += r[y];
        r[y] = x;
        return true;
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int getTreeSize(const int x) const {
        return -r[getRoot(x)];
    }
};


const int maxN = 1e5 + 5, maxP = 1e7 + 7, inf = 0x3f3f3f3f, ninf = 0xc0c0c0c0;

int n, mxp, p[maxN], k[maxP];
DisjointSet dsu(maxP);
vii e[maxP];

void input() {
    cin >> n;
    fort(i, 1, n) {
        cin >> p[i];
        k[p[i]] = p[i];
        maxi(mxp, p[i]);
    }
}

void subtask1() {
    /**
        Prim algorithm

        min(x % y, y % x) = max(x, y) % min(x, y)

    **/
    const int N = n + 5;
    int x;
    ll res = 0;
    vi d(N, inf);
    vector<bool> vis(N);
    d[1] = 0;
    fort(_, 1, n) {
        x = -1;
        fort(i, 1, n) {
            if (vis[i])
                continue;
            if (x < 0 || d[x] > d[i])
                x = i;
        }
        vis[x] = true;
        res += d[x];
        fort(i, 1, n) {
            if (vis[i])
                continue;
            mini(d[i], min(p[x] % p[i], p[i] % p[x]));
        }
    }
    cout << res << '\n';
}

void subtask3() {
    ll res = 0;
    for (int i = mxp - 1, j; i >= 1; --i)
        if (!k[i])
            k[i] = k[i + 1];
        else {
            j = i << 1;
            if (i < mxp) {                           // for case i only add edge from i to a vertex with value in [i + 1, i * 2 - 1]
                if (j > mxp || k[i + 1] != k[j])     // check if there is a vertex with value in [i + 1, j - 1]
                    e[k[i + 1] - i].emplace_back(i, k[i + 1]);
            }
            for (; j <= mxp; j += i)                 // for case j = i * t (i >= 2), add edge from j to a vertex with value in [j, j + i - 1]
                if (j + i > mxp || k[j] != k[j + i]) // check if there is a vertex with value in [j, j + i - 1]
                    e[k[j] - j].emplace_back(i, k[j]);
        }
    fort(w, 0, mxp)
        for (const auto &[x, y] : e[w])
            if (dsu.unite(x, y))
                res += w;
    cout << res << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
    if (n <= 7500)
        subtask1();
    else
        subtask3();
    return 0;
}

Compilation message

sirni.cpp: In function 'void subtask3()':
sirni.cpp:155:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |         for (const auto &[x, y] : e[w])
      |                          ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 277940 KB Output is correct
2 Correct 135 ms 276280 KB Output is correct
3 Correct 134 ms 278176 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 274272 KB Output is correct
2 Correct 130 ms 274748 KB Output is correct
3 Correct 129 ms 278172 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 278128 KB Output is correct
2 Correct 135 ms 276688 KB Output is correct
3 Correct 138 ms 278188 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 288772 KB Output is correct
2 Correct 214 ms 316772 KB Output is correct
3 Correct 187 ms 292936 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 280012 KB Output is correct
2 Correct 190 ms 302076 KB Output is correct
3 Correct 152 ms 286948 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 300808 KB Output is correct
2 Correct 259 ms 328164 KB Output is correct
3 Correct 171 ms 292476 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 278568 KB Output is correct
2 Correct 232 ms 328732 KB Output is correct
3 Correct 163 ms 291420 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 327116 KB Output is correct
2 Correct 1081 ms 517024 KB Output is correct
3 Correct 277 ms 329800 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 327060 KB Output is correct
2 Correct 1427 ms 633580 KB Output is correct
3 Correct 317 ms 334068 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 315920 KB Output is correct
2 Correct 1387 ms 638396 KB Output is correct
3 Correct 240 ms 293588 KB Output is correct