oj.uz

Submission #596898

# Submission time Handle Problem Language Result Execution time Memory
596898 2022-07-15T09:05:10 Z 이동현(#8450) Reconstruction Project (JOI22_reconstruction) C++17
42 / 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[y] = x;
    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;
    //n = 500, m = 499;
    for(int i = 0; i < m; ++i){
        way[i].resize(3);
        cin >> way[i][1] >> way[i][2] >> way[i][0];
        //way[i][1] = i + 1, way[i][2] = i + 2, way[i][0] = i + 30;
        l[i] = -1, r[i] = m;
    }
    cin >> q; //q = 1000000;
    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;
        }
    }
    int rp = 0;
    while(q--){
        int x; cin >> x;
        //x = q + 100;
        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;
        assert(lid <= 500 && rid <= 500);
        lst[lid + 1] = (int)2e9, rst[rid + 1] = -100;
        long long ans = 0;
        while(cnt < n - 1){
            while(lid > 0 && r[lst[lid]] < rst[rid + 1]){
                --lid;
            }
            while(rid > 0 && l[rst[rid]] > lst[lid + 1]){
                --rid;
            }
            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;
        }
        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 1 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 3412 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 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 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 1 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 3412 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 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 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 1705 ms 7356 KB Output is correct
21 Correct 809 ms 7348 KB Output is correct
22 Correct 816 ms 7352 KB Output is correct
23 Correct 930 ms 7368 KB Output is correct
24 Correct 1233 ms 7344 KB Output is correct
25 Correct 1585 ms 7344 KB Output is correct
26 Correct 1695 ms 7356 KB Output is correct
27 Correct 1691 ms 7372 KB Output is correct
28 Correct 1650 ms 7348 KB Output is correct
29 Correct 617 ms 7348 KB Output is correct
30 Correct 1716 ms 7352 KB Output is correct
31 Correct 1720 ms 7356 KB Output is correct
32 Correct 1754 ms 7356 KB Output is correct
33 Correct 1678 ms 7348 KB Output is correct
34 Correct 746 ms 7352 KB Output is correct
35 Correct 1714 ms 7348 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 5055 ms 11548 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 3412 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 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 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 4676 ms 15704 KB Output is correct
21 Correct 4751 ms 15868 KB Output is correct
22 Correct 4897 ms 15748 KB Output is correct
23 Correct 4926 ms 15792 KB Output is correct
24 Correct 4909 ms 15720 KB Output is correct
25 Correct 4936 ms 15748 KB Output is correct
26 Correct 4632 ms 15652 KB Output is correct
27 Correct 3614 ms 15704 KB Output is correct
28 Correct 4929 ms 15716 KB Output is correct
29 Correct 4873 ms 15692 KB Output is correct
30 Correct 4865 ms 15732 KB Output is correct
31 Correct 4831 ms 15732 KB Output is correct
32 Correct 2821 ms 16244 KB Output is correct
33 Execution timed out 5055 ms 13276 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 3412 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 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 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 1705 ms 7356 KB Output is correct
21 Correct 809 ms 7348 KB Output is correct
22 Correct 816 ms 7352 KB Output is correct
23 Correct 930 ms 7368 KB Output is correct
24 Correct 1233 ms 7344 KB Output is correct
25 Correct 1585 ms 7344 KB Output is correct
26 Correct 1695 ms 7356 KB Output is correct
27 Correct 1691 ms 7372 KB Output is correct
28 Correct 1650 ms 7348 KB Output is correct
29 Correct 617 ms 7348 KB Output is correct
30 Correct 1716 ms 7352 KB Output is correct
31 Correct 1720 ms 7356 KB Output is correct
32 Correct 1754 ms 7356 KB Output is correct
33 Correct 1678 ms 7348 KB Output is correct
34 Correct 746 ms 7352 KB Output is correct
35 Correct 1714 ms 7348 KB Output is correct
36 Correct 2180 ms 7476 KB Output is correct
37 Correct 1094 ms 7476 KB Output is correct
38 Correct 1189 ms 7444 KB Output is correct
39 Correct 1324 ms 7484 KB Output is correct
40 Correct 1661 ms 7476 KB Output is correct
41 Correct 2136 ms 7548 KB Output is correct
42 Correct 2101 ms 7476 KB Output is correct
43 Correct 2096 ms 7532 KB Output is correct
44 Correct 1964 ms 7496 KB Output is correct
45 Correct 830 ms 7580 KB Output is correct
46 Correct 2263 ms 7472 KB Output is correct
47 Correct 2298 ms 7528 KB Output is correct
48 Correct 2159 ms 7532 KB Output is correct
49 Correct 2088 ms 7544 KB Output is correct
50 Correct 828 ms 7564 KB Output is correct
51 Correct 1818 ms 7432 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 3412 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 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 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 1705 ms 7356 KB Output is correct
21 Correct 809 ms 7348 KB Output is correct
22 Correct 816 ms 7352 KB Output is correct
23 Correct 930 ms 7368 KB Output is correct
24 Correct 1233 ms 7344 KB Output is correct
25 Correct 1585 ms 7344 KB Output is correct
26 Correct 1695 ms 7356 KB Output is correct
27 Correct 1691 ms 7372 KB Output is correct
28 Correct 1650 ms 7348 KB Output is correct
29 Correct 617 ms 7348 KB Output is correct
30 Correct 1716 ms 7352 KB Output is correct
31 Correct 1720 ms 7356 KB Output is correct
32 Correct 1754 ms 7356 KB Output is correct
33 Correct 1678 ms 7348 KB Output is correct
34 Correct 746 ms 7352 KB Output is correct
35 Correct 1714 ms 7348 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 5055 ms 11548 KB Time limit exceeded
40 Halted 0 ms 0 KB -