Submission #596909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
596909	2022-07-15T09:14:53 Z	이동현(#8450)	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5000 ms	16008 KB

reconstruction

#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;
        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
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	3412 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	3412 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 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	5076 ms	16008 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-