Submission #951560

#	Time	Username	Problem	Language	Result	Execution time	Memory
951560		Darren0724	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5036 ms	14788 KiB

reconstruction

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx","avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long 
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=505;
const int M=1000005;
const ll INF=1e18;
struct DSU{
    vector<int> pa,sz;
    DSU(int n){
        pa.resize(n);
        sz.resize(n,1);
        iota(all(pa),0);
    }
    int Find(int k){
        return (k==pa[k]?k:pa[k]=Find(pa[k]));
    }
    void onion(int a,int b){
        a=Find(a),b=Find(b);
        if(a==b)return;
        if(sz[a]>sz[b]){
            swap(a,b);
        }
        pa[a]=b;
        sz[b]+=sz[a];
    }
    int same(int a,int b){
        return Find(a)==Find(b);
    }
};  
int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<array<int,3>> v(m);
    for(int i=0;i<m;i++){
        cin>>v[i][1]>>v[i][2]>>v[i][0];
    }
    sort(all(v));
    int ptr=0;
    int q;cin>>q;
    for(int q1=0;q1<q;q1++){
        int x;cin>>x;
        while(ptr<m&&v[ptr][0]<=x){
            ptr++;
        }
        DSU dsu(n+1);
        ll ans=0;
        int l=ptr-1,r=ptr;
        while(l>=0&&r<m){
            if(abs(x-v[l][0])<abs(x-v[r][0])){
                if(!dsu.same(v[l][1],v[l][2])){
                    dsu.onion(v[l][1],v[l][2]);
                    ans+=abs(x-v[l][0]);
                }
                l--;
            }
            else{
                if(!dsu.same(v[r][1],v[r][2])){
                    dsu.onion(v[r][1],v[r][2]);
                    ans+=abs(x-v[r][0]);
                }
                r++;
            }   
        }
        while(l>=0){
            if(!dsu.same(v[l][1],v[l][2])){
                dsu.onion(v[l][1],v[l][2]);
                ans+=abs(x-v[l][0]);
            }
            l--;
        }
        while(r<m){
            if(!dsu.same(v[r][1],v[r][2])){
                dsu.onion(v[r][1],v[r][2]);
                ans+=abs(x-v[r][0]);
            }
            r++;
        }
        cout<<ans<<endl;
    }   


    
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23