oj.uz

Submission #575125

# Submission time Handle Problem Language Result Execution time Memory
575125 2022-06-09T17:21:36 Z Sorting Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 400504 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 500 + 3;
const int M = 1e5 + 3;
const int Q = 1e6 + 3;
const int INF = 1e9;

int n, m, q;
array<ll, 3> e[M];
ll x[Q];

struct DSU{
    int sz[N], par[N];

    void init(int n){
        for(int i = 1; i <= n; ++i)
            sz[i] = 1, par[i] = i;
    }

    int getP(int x){
        if(par[x] == x) return x;
        return par[x] = getP(par[x]);
    }

    bool unite(int a, int b){
        a = getP(a), b = getP(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
        return true;
    }
} dsu;

int pr[M][N], su[M][N];
int pr_cnt[M], su_cnt[M];

inline void try_dsu(DSU &dsu, int cost, int idx, ll &ans, int &cnt){
    if(dsu.unite(e[idx][1], e[idx][2])){
        ans += cost;
        ++cnt;
    }
}

ll get_ans(int *e1, int *e2, ll x, int ptr){
    ll ans = 0;

    int e1_sz = (ptr >= 1) ? pr_cnt[ptr - 1] : 0;
    int e2_sz = (ptr <= m - 1) ? su_cnt[ptr] : 0;

    dsu.init(n);

    int ptr1 = 0, ptr2 = 0, cnt = 0;
    while(ptr1 != e1_sz && ptr2 != e2_sz && cnt < n - 1){
        int cost1 = x - e[e1[ptr1]][0];
        int cost2 = e[e2[ptr2]][0] - x;

        if(cost1 < cost2)
            try_dsu(dsu, cost1, e1[ptr1++], ans, cnt);
        else
            try_dsu(dsu, cost2, e2[ptr2++], ans, cnt);
    }
    while(ptr1 != e1_sz && cnt < n - 1){
        int cost1 = x - e[e1[ptr1]][0];
        try_dsu(dsu, cost1, e1[ptr1++], ans, cnt);
    }
    while(ptr2 != e2_sz && cnt < n - 1){
        int cost2 = e[e2[ptr2]][0] - x;
        try_dsu(dsu, cost2, e2[ptr2++], ans, cnt);
    }

    return ans;
}

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

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

    pr[0][0] = 0;
    pr_cnt[0] = 1;
    for(int i = 1; i < m; ++i){
        dsu.init(n);
        pr[i][pr_cnt[i]++] = i;

        for(int j = 0; j < pr_cnt[i - 1]; ++j){
            int idx = pr[i - 1][j];
            if(dsu.unite(e[idx][1], e[idx][2]))
                pr[i][pr_cnt[i]++] = idx;
        }
    }

    su[m - 1][0] = m - 1;
    su_cnt[m - 1] = 1;
    for(int i = m - 2; i >= 0; --i){
        dsu.init(n);
        su[i][su_cnt[i]++] = i;

        for(int j = 0; j < su_cnt[i + 1]; ++j){
            int idx = su[i + 1][j];
            if(dsu.unite(e[idx][1], e[idx][2]))
                su[i][su_cnt[i]++] = idx;
        }
    }

    int ptr = 0;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> x[i];
        while(ptr != m && x[i] >= e[ptr][0])
            ++ptr;

        int *e1;
        if(0 <= ptr - 1){
            e1 = pr[ptr - 1];
        }
        int *e2;
        if(ptr <= m - 1){
            e2 = su[ptr];
        }

        auto ans = get_ans(e1, e2, x[i], ptr);

        cout << ans << "\n";
    }
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:134:27: warning: 'e2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |         auto ans = get_ans(e1, e2, x[i], ptr);
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:134:27: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1754 ms 397264 KB Output is correct
21 Correct 1574 ms 397096 KB Output is correct
22 Correct 1656 ms 397280 KB Output is correct
23 Correct 1641 ms 397244 KB Output is correct
24 Correct 1666 ms 397200 KB Output is correct
25 Correct 1728 ms 397388 KB Output is correct
26 Correct 1746 ms 397132 KB Output is correct
27 Correct 1744 ms 397104 KB Output is correct
28 Correct 1723 ms 397224 KB Output is correct
29 Correct 1566 ms 397176 KB Output is correct
30 Correct 1762 ms 397168 KB Output is correct
31 Correct 1749 ms 397168 KB Output is correct
32 Correct 1745 ms 397188 KB Output is correct
33 Correct 1743 ms 397184 KB Output is correct
34 Correct 1265 ms 397132 KB Output is correct
35 Correct 1736 ms 397260 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Execution timed out 5095 ms 400504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5077 ms 14760 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1754 ms 397264 KB Output is correct
21 Correct 1574 ms 397096 KB Output is correct
22 Correct 1656 ms 397280 KB Output is correct
23 Correct 1641 ms 397244 KB Output is correct
24 Correct 1666 ms 397200 KB Output is correct
25 Correct 1728 ms 397388 KB Output is correct
26 Correct 1746 ms 397132 KB Output is correct
27 Correct 1744 ms 397104 KB Output is correct
28 Correct 1723 ms 397224 KB Output is correct
29 Correct 1566 ms 397176 KB Output is correct
30 Correct 1762 ms 397168 KB Output is correct
31 Correct 1749 ms 397168 KB Output is correct
32 Correct 1745 ms 397188 KB Output is correct
33 Correct 1743 ms 397184 KB Output is correct
34 Correct 1265 ms 397132 KB Output is correct
35 Correct 1736 ms 397260 KB Output is correct
36 Correct 2192 ms 397684 KB Output is correct
37 Correct 2017 ms 397620 KB Output is correct
38 Correct 2122 ms 397624 KB Output is correct
39 Correct 2121 ms 397704 KB Output is correct
40 Correct 2158 ms 397512 KB Output is correct
41 Correct 2182 ms 397756 KB Output is correct
42 Correct 2173 ms 397740 KB Output is correct
43 Correct 2191 ms 397768 KB Output is correct
44 Correct 2049 ms 397524 KB Output is correct
45 Correct 1709 ms 397736 KB Output is correct
46 Correct 2177 ms 397676 KB Output is correct
47 Correct 2164 ms 397692 KB Output is correct
48 Correct 2155 ms 397564 KB Output is correct
49 Correct 2157 ms 397660 KB Output is correct
50 Correct 1364 ms 397620 KB Output is correct
51 Correct 1992 ms 397556 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1754 ms 397264 KB Output is correct
21 Correct 1574 ms 397096 KB Output is correct
22 Correct 1656 ms 397280 KB Output is correct
23 Correct 1641 ms 397244 KB Output is correct
24 Correct 1666 ms 397200 KB Output is correct
25 Correct 1728 ms 397388 KB Output is correct
26 Correct 1746 ms 397132 KB Output is correct
27 Correct 1744 ms 397104 KB Output is correct
28 Correct 1723 ms 397224 KB Output is correct
29 Correct 1566 ms 397176 KB Output is correct
30 Correct 1762 ms 397168 KB Output is correct
31 Correct 1749 ms 397168 KB Output is correct
32 Correct 1745 ms 397188 KB Output is correct
33 Correct 1743 ms 397184 KB Output is correct
34 Correct 1265 ms 397132 KB Output is correct
35 Correct 1736 ms 397260 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Execution timed out 5095 ms 400504 KB Time limit exceeded
40 Halted 0 ms 0 KB -