oj.uz

Submission #575119

# Submission time Handle Problem Language Result Execution time Memory
575119 2022-06-09T17:17:50 Z Sorting Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 400372 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];

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

ll get_ans(int *e1, int *e2, ll x, int ptr){
    ll ans = 0;
    int cnt = 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;
    while(ptr1 != e1_sz && ptr2 != e2_sz){
        int cost1 = x - e[e1[ptr1]][0];
        int cost2 = e[e2[ptr2]][0] - x;

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

    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 'll get_ans(int*, int*, ll, int)':
reconstruction.cpp:53:9: warning: unused variable 'cnt' [-Wunused-variable]
   53 |     int cnt = 0;
      |         ^~~
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 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 332 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 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1767 ms 397804 KB Output is correct
21 Correct 1590 ms 398828 KB Output is correct
22 Correct 1648 ms 399004 KB Output is correct
23 Correct 1633 ms 398984 KB Output is correct
24 Correct 1693 ms 398896 KB Output is correct
25 Correct 1831 ms 398796 KB Output is correct
26 Correct 1747 ms 398888 KB Output is correct
27 Correct 1751 ms 398800 KB Output is correct
28 Correct 1719 ms 398768 KB Output is correct
29 Correct 1575 ms 398940 KB Output is correct
30 Correct 1729 ms 398904 KB Output is correct
31 Correct 1726 ms 398960 KB Output is correct
32 Correct 1727 ms 398968 KB Output is correct
33 Correct 1744 ms 398944 KB Output is correct
34 Correct 1276 ms 399008 KB Output is correct
35 Correct 1738 ms 398916 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 1 ms 340 KB Output is correct
4 Execution timed out 5078 ms 400372 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 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 332 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 5063 ms 16692 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 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1767 ms 397804 KB Output is correct
21 Correct 1590 ms 398828 KB Output is correct
22 Correct 1648 ms 399004 KB Output is correct
23 Correct 1633 ms 398984 KB Output is correct
24 Correct 1693 ms 398896 KB Output is correct
25 Correct 1831 ms 398796 KB Output is correct
26 Correct 1747 ms 398888 KB Output is correct
27 Correct 1751 ms 398800 KB Output is correct
28 Correct 1719 ms 398768 KB Output is correct
29 Correct 1575 ms 398940 KB Output is correct
30 Correct 1729 ms 398904 KB Output is correct
31 Correct 1726 ms 398960 KB Output is correct
32 Correct 1727 ms 398968 KB Output is correct
33 Correct 1744 ms 398944 KB Output is correct
34 Correct 1276 ms 399008 KB Output is correct
35 Correct 1738 ms 398916 KB Output is correct
36 Correct 2197 ms 399572 KB Output is correct
37 Correct 2005 ms 399548 KB Output is correct
38 Correct 2110 ms 399516 KB Output is correct
39 Correct 2145 ms 399520 KB Output is correct
40 Correct 2163 ms 399436 KB Output is correct
41 Correct 2181 ms 399372 KB Output is correct
42 Correct 2199 ms 399616 KB Output is correct
43 Correct 2213 ms 399344 KB Output is correct
44 Correct 2065 ms 399448 KB Output is correct
45 Correct 1770 ms 399512 KB Output is correct
46 Correct 2195 ms 399424 KB Output is correct
47 Correct 2227 ms 399512 KB Output is correct
48 Correct 2195 ms 399508 KB Output is correct
49 Correct 2209 ms 399532 KB Output is correct
50 Correct 1355 ms 399604 KB Output is correct
51 Correct 2050 ms 399692 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 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1767 ms 397804 KB Output is correct
21 Correct 1590 ms 398828 KB Output is correct
22 Correct 1648 ms 399004 KB Output is correct
23 Correct 1633 ms 398984 KB Output is correct
24 Correct 1693 ms 398896 KB Output is correct
25 Correct 1831 ms 398796 KB Output is correct
26 Correct 1747 ms 398888 KB Output is correct
27 Correct 1751 ms 398800 KB Output is correct
28 Correct 1719 ms 398768 KB Output is correct
29 Correct 1575 ms 398940 KB Output is correct
30 Correct 1729 ms 398904 KB Output is correct
31 Correct 1726 ms 398960 KB Output is correct
32 Correct 1727 ms 398968 KB Output is correct
33 Correct 1744 ms 398944 KB Output is correct
34 Correct 1276 ms 399008 KB Output is correct
35 Correct 1738 ms 398916 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Execution timed out 5078 ms 400372 KB Time limit exceeded
40 Halted 0 ms 0 KB -