oj.uz

Submission #596854

# Submission time Handle Problem Language Result Execution time Memory
596854 2022-07-15T07:53:53 Z 이동현(#8450) Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 16244 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize9("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int MS = (int)1e5 + 4;
int n, m, q;
vector<int> way[MS];
int l[MS], r[MS];
int rst[504], rstN, lev[MS], rev[MS];
int lst[504], lstN;

int pr[504];

inline int fd(int x){
    return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}

inline bool unite(int x, int y){
    x = fd(x), y = fd(y);
    if(x == y) return false;
    pr[x] = y;
    return true;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    memset(lev, -1, sizeof(lev)), memset(rev, -1, sizeof(rev));
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        way[i].resize(3);
        cin >> way[i][1] >> way[i][2] >> way[i][0];
        l[i] = -1, r[i] = m;
    }
    sort(way, way + m);
    for(int i = 0; i < m; ++i){
        for(int i = 1; i <= n; ++i){
            pr[i] = i;
        }
        unite(way[i][1], way[i][2]);
        int pos = lstN;
        while(pos){
            if(!unite(way[lst[pos]][1], way[lst[pos]][2])){
                break;
            }
            --pos;
        }
        if(pos){
            lev[i] = lst[pos];
            l[i] = lev[i] + 1;
            for(int k = pos; k < lstN; ++k){
                lst[k] = lst[k + 1];
            }
            lst[lstN] = i;
        }
        else{
            l[i] = -1;
            lst[++lstN] = i;
        }
    }
    lstN = 0;
    for(int i = m - 1; i >= 0; --i){
        if(rstN >= n - 1){
            r[i] = rst[1] - 1;
        }
        for(int i = 1; i <= n; ++i){
            pr[i] = i;
        }
        unite(way[i][1], way[i][2]);
        int pos = rstN;
        while(pos){
            if(!unite(way[rst[pos]][1], way[rst[pos]][2])){
                break;
            }
            --pos;
        }
        if(pos){
            rev[i] = rst[pos];
            r[i] = rev[i] - 1;
            for(int k = pos; k < rstN; ++k){
                rst[k] = rst[k + 1];
            }
            rst[rstN] = i;
        }
        else{
            r[i] = m;
            rst[++rstN] = i;
        }
    }
    cin >> q;
    int rp = 0;
    while(q--){
        int x; cin >> x;
        while(rp < m && way[rp][0] < x){
            if(rev[rp] == -1){
                --rstN;
            }
            else{
                for(int i = rstN; ; --i){
                    if(i > 1 && rst[i - 1] < rev[rp]){
                        rst[i] = rst[i - 1];
                    }
                    else{
                        rst[i] = rev[rp];
                        break;
                    }
                }
            }
            if(lev[rp] == -1){
                lst[++lstN] = rp;
            }
            else{
                int pos = lower_bound(lst + 1, lst + lstN + 1, lev[rp]) - lst;
                for(int i = pos; i < lstN; ++i){
                    lst[i] = lst[i + 1];
                }
                lst[lstN] = rp;
            }
            ++rp;
        }
        int lid = lstN, rid = rstN, cnt = 0;
        lst[lid + 1] = (int)2e9, rst[rid + 1] = -100;
        long long ans = 0;
        T:
            if(lid > 0 && r[lst[lid]] < rst[rid + 1]){
                --lid; goto T;
            }
        T2:
            if(rid > 0 && l[rst[rid]] > lst[lid + 1]){
                --rid; goto T2;
            }
            if(!rid || (lid && x - way[lst[lid]][0] < way[rst[rid]][0] - x)){
                ans += x - way[lst[lid]][0];
                --lid;
            }
            else{
                ans += way[rst[rid]][0] - x;
                --rid;
            }
            ++cnt;
        if(cnt < n - 1) goto T;
        cout << ans << '\n';
    }
    return 0;
}

Compilation message

reconstruction.cpp:3: warning: ignoring '#pragma GCC optimize9' [-Wunknown-pragmas]
    3 | #pragma GCC optimize9("Ofast")
      |

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3392 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 1644 ms 7348 KB Output is correct
21 Correct 791 ms 7352 KB Output is correct
22 Correct 791 ms 7352 KB Output is correct
23 Correct 908 ms 7348 KB Output is correct
24 Correct 1170 ms 7348 KB Output is correct
25 Correct 1603 ms 7344 KB Output is correct
26 Correct 1684 ms 7344 KB Output is correct
27 Correct 1691 ms 7344 KB Output is correct
28 Correct 1626 ms 7348 KB Output is correct
29 Correct 905 ms 7348 KB Output is correct
30 Correct 1653 ms 7352 KB Output is correct
31 Correct 1656 ms 7352 KB Output is correct
32 Correct 1666 ms 7344 KB Output is correct
33 Correct 1615 ms 7348 KB Output is correct
34 Correct 1177 ms 7348 KB Output is correct
35 Correct 1674 ms 7352 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3392 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 3268 ms 15664 KB Output is correct
21 Correct 3121 ms 15884 KB Output is correct
22 Correct 3629 ms 15708 KB Output is correct
23 Correct 3647 ms 15824 KB Output is correct
24 Correct 3348 ms 15768 KB Output is correct
25 Correct 3302 ms 15708 KB Output is correct
26 Correct 3253 ms 15744 KB Output is correct
27 Correct 2573 ms 15784 KB Output is correct
28 Correct 3552 ms 15700 KB Output is correct
29 Correct 3526 ms 15760 KB Output is correct
30 Correct 3309 ms 15820 KB Output is correct
31 Correct 3382 ms 15712 KB Output is correct
32 Correct 2520 ms 16244 KB Output is correct
33 Correct 3588 ms 15512 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3392 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 1644 ms 7348 KB Output is correct
21 Correct 791 ms 7352 KB Output is correct
22 Correct 791 ms 7352 KB Output is correct
23 Correct 908 ms 7348 KB Output is correct
24 Correct 1170 ms 7348 KB Output is correct
25 Correct 1603 ms 7344 KB Output is correct
26 Correct 1684 ms 7344 KB Output is correct
27 Correct 1691 ms 7344 KB Output is correct
28 Correct 1626 ms 7348 KB Output is correct
29 Correct 905 ms 7348 KB Output is correct
30 Correct 1653 ms 7352 KB Output is correct
31 Correct 1656 ms 7352 KB Output is correct
32 Correct 1666 ms 7344 KB Output is correct
33 Correct 1615 ms 7348 KB Output is correct
34 Correct 1177 ms 7348 KB Output is correct
35 Correct 1674 ms 7352 KB Output is correct
36 Correct 1845 ms 7520 KB Output is correct
37 Correct 972 ms 7604 KB Output is correct
38 Correct 954 ms 7536 KB Output is correct
39 Correct 1135 ms 7476 KB Output is correct
40 Correct 1422 ms 7464 KB Output is correct
41 Correct 1784 ms 7612 KB Output is correct
42 Correct 1877 ms 7524 KB Output is correct
43 Correct 1888 ms 7540 KB Output is correct
44 Correct 1743 ms 7468 KB Output is correct
45 Correct 938 ms 7512 KB Output is correct
46 Correct 1812 ms 7524 KB Output is correct
47 Correct 1880 ms 7520 KB Output is correct
48 Correct 1834 ms 7636 KB Output is correct
49 Correct 1830 ms 7520 KB Output is correct
50 Correct 1166 ms 7604 KB Output is correct
51 Correct 1735 ms 7476 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3392 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 1644 ms 7348 KB Output is correct
21 Correct 791 ms 7352 KB Output is correct
22 Correct 791 ms 7352 KB Output is correct
23 Correct 908 ms 7348 KB Output is correct
24 Correct 1170 ms 7348 KB Output is correct
25 Correct 1603 ms 7344 KB Output is correct
26 Correct 1684 ms 7344 KB Output is correct
27 Correct 1691 ms 7344 KB Output is correct
28 Correct 1626 ms 7348 KB Output is correct
29 Correct 905 ms 7348 KB Output is correct
30 Correct 1653 ms 7352 KB Output is correct
31 Correct 1656 ms 7352 KB Output is correct
32 Correct 1666 ms 7344 KB Output is correct
33 Correct 1615 ms 7348 KB Output is correct
34 Correct 1177 ms 7348 KB Output is correct
35 Correct 1674 ms 7352 KB Output is correct
36 Correct 2 ms 3412 KB Output is correct
37 Correct 2 ms 3412 KB Output is correct
38 Correct 2 ms 3412 KB Output is correct
39 Execution timed out 5046 ms 13424 KB Time limit exceeded
40 Halted 0 ms 0 KB -