oj.uz

Submission #704706

# Submission time Handle Problem Language Result Execution time Memory
704706 2023-03-02T17:14:07 Z piOOE Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 621460 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int Q = 1e6 + 1, N = 500;

vector<array<int, 3>> save[Q];
array<int, 3> e[Q];

int fa[N];

void init() {
    iota(fa, fa + N, 0);
}

int leader(int x) {
//    while (x != fa[x]) x = fa[x] = fa[fa[x]];
    return x == fa[x] ? x : fa[x] = leader(fa[x]);
}

bool unite(int x, int y) {
    x = leader(x), y = leader(y);

    if (x == y) {
        return false;
    }

    fa[y] = x;

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
        e[i][1] -= 1, e[i][2] -= 1;
    }

    sort(e, e + m);

    int q;
    cin >> q;

    vector<int> X(q);
    vector<ll> ans(q);

    for (int &x : X) {
        cin >> x;
    }

    constexpr int inf = 2e9;

    for (int t = 0; t < 2; ++t) {
        vector<array<int, 3>> mst;

        int pnt = 0;

        for (int i = 0; i <= m; ++i) {
            if (i > 0) {
                mst.insert(mst.begin(), e[(t == 0 ? m - i : i - 1)]);
                init();

                for (int ii = 0; ii < mst.size(); ++ii) {
                    if (!unite(mst[ii][1], mst[ii][2])) {
                        mst.erase(mst.begin() + ii);
                        break;
                    }
                }

                if (t == 0) {
                    save[m - i] = mst;
                }
            }

            if (t == 1) {
                auto &oth = save[i];

                while (pnt < q && X[pnt] < (i == m ? inf : e[i][0])) {
                    init();

                    int L = 0, R = 0, cnt = 0;

                    while (cnt < n - 1) {
                        int weightL = L == mst.size() ? inf : X[pnt] - mst[L][0];
                        int weightR = R == oth.size() ? inf : oth[R][0] - X[pnt];

                        if (weightL < weightR) {
                            if (unite(mst[L][1], mst[L][2])) {
                                ans[pnt] += weightL;
                                cnt += 1;
                            }

                            L += 1;
                        } else {
                            if (unite(oth[R][1], oth[R][2])) {
                                ans[pnt] += weightR;
                                cnt += 1;
                            }

                            R += 1;
                        }
                    }

                    pnt += 1;
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:70:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for (int ii = 0; ii < mst.size(); ++ii) {
      |                                  ~~~^~~~~~~~~~~~
reconstruction.cpp:91:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                         int weightL = L == mst.size() ? inf : X[pnt] - mst[L][0];
      |                                       ~~^~~~~~~~~~~~~
reconstruction.cpp:92:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                         int weightR = R == oth.size() ? inf : oth[R][0] - X[pnt];
      |                                       ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 12 ms 23796 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 11 ms 23712 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 11 ms 23736 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 14 ms 23748 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 12 ms 23796 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 11 ms 23712 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 11 ms 23736 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 14 ms 23748 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 1453 ms 610396 KB Output is correct
21 Correct 763 ms 581056 KB Output is correct
22 Correct 765 ms 604720 KB Output is correct
23 Correct 850 ms 609408 KB Output is correct
24 Correct 1082 ms 610220 KB Output is correct
25 Correct 1421 ms 610388 KB Output is correct
26 Correct 1442 ms 610636 KB Output is correct
27 Correct 1417 ms 610764 KB Output is correct
28 Correct 1442 ms 610488 KB Output is correct
29 Correct 679 ms 590792 KB Output is correct
30 Correct 1423 ms 610532 KB Output is correct
31 Correct 1422 ms 610664 KB Output is correct
32 Correct 1433 ms 610624 KB Output is correct
33 Correct 1422 ms 610588 KB Output is correct
34 Correct 641 ms 417532 KB Output is correct
35 Correct 1433 ms 610704 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 14 ms 23892 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Execution timed out 5061 ms 621460 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 12 ms 23796 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 11 ms 23712 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 11 ms 23736 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 14 ms 23748 KB Output is correct
19 Correct 13 ms 23764 KB Output is correct
20 Execution timed out 5034 ms 40692 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 12 ms 23796 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 11 ms 23712 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 11 ms 23736 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 14 ms 23748 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 1453 ms 610396 KB Output is correct
21 Correct 763 ms 581056 KB Output is correct
22 Correct 765 ms 604720 KB Output is correct
23 Correct 850 ms 609408 KB Output is correct
24 Correct 1082 ms 610220 KB Output is correct
25 Correct 1421 ms 610388 KB Output is correct
26 Correct 1442 ms 610636 KB Output is correct
27 Correct 1417 ms 610764 KB Output is correct
28 Correct 1442 ms 610488 KB Output is correct
29 Correct 679 ms 590792 KB Output is correct
30 Correct 1423 ms 610532 KB Output is correct
31 Correct 1422 ms 610664 KB Output is correct
32 Correct 1433 ms 610624 KB Output is correct
33 Correct 1422 ms 610588 KB Output is correct
34 Correct 641 ms 417532 KB Output is correct
35 Correct 1433 ms 610704 KB Output is correct
36 Correct 2005 ms 611388 KB Output is correct
37 Correct 1178 ms 585000 KB Output is correct
38 Correct 1223 ms 604468 KB Output is correct
39 Correct 1405 ms 609892 KB Output is correct
40 Correct 1638 ms 610868 KB Output is correct
41 Correct 2035 ms 611160 KB Output is correct
42 Correct 2015 ms 611332 KB Output is correct
43 Correct 1987 ms 611276 KB Output is correct
44 Correct 1789 ms 611384 KB Output is correct
45 Correct 833 ms 591504 KB Output is correct
46 Correct 2004 ms 611384 KB Output is correct
47 Correct 2012 ms 611644 KB Output is correct
48 Correct 2021 ms 611684 KB Output is correct
49 Correct 1993 ms 611656 KB Output is correct
50 Correct 779 ms 418812 KB Output is correct
51 Correct 1690 ms 611664 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 12 ms 23796 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 11 ms 23712 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 11 ms 23736 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 14 ms 23748 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 1453 ms 610396 KB Output is correct
21 Correct 763 ms 581056 KB Output is correct
22 Correct 765 ms 604720 KB Output is correct
23 Correct 850 ms 609408 KB Output is correct
24 Correct 1082 ms 610220 KB Output is correct
25 Correct 1421 ms 610388 KB Output is correct
26 Correct 1442 ms 610636 KB Output is correct
27 Correct 1417 ms 610764 KB Output is correct
28 Correct 1442 ms 610488 KB Output is correct
29 Correct 679 ms 590792 KB Output is correct
30 Correct 1423 ms 610532 KB Output is correct
31 Correct 1422 ms 610664 KB Output is correct
32 Correct 1433 ms 610624 KB Output is correct
33 Correct 1422 ms 610588 KB Output is correct
34 Correct 641 ms 417532 KB Output is correct
35 Correct 1433 ms 610704 KB Output is correct
36 Correct 13 ms 23816 KB Output is correct
37 Correct 14 ms 23892 KB Output is correct
38 Correct 14 ms 23808 KB Output is correct
39 Execution timed out 5061 ms 621460 KB Time limit exceeded
40 Halted 0 ms 0 KB -