제출 #1029723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029723		shenfe1	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5097 ms	3052 KiB

reconstruction

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define ppb pop_back
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define lb lower_bound
// #define int ll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX=2e5+10;

int n,m;
vector<pair<int,pii>> e;

struct DSU{
    int f[MAX];

    void init(int n){
        for(int i=1;i<=n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }

    void unite(int a,int b){
        a=get(a);
        b=get(b);
        if(rng()%2)swap(a,b);
        f[a]=b;
    }
}D;

int make(int a,pii x){
    if(D.get(x.F)!=D.get(x.S)){
        D.unite(x.F,x.S);
        return a;
    }
    return 0;
}

ll solve(int d){
    int r=lb(all(e),make_pair(d,make_pair(0,0)))-e.begin();
    int l=r-1;
    D.init(n);
    ll ans=0;
    for(int i=1;i<=m;i++){
        if(r<sz(e)&&l>=0){
            if(e[r].F-d<=d-e[l].F){
                ans+=make(e[r].F-d,e[r].S);
                r++;
            }
            else{
                ans+=make(d-e[l].F,e[l].S);
                l--;
            }
        }
        else if(r<sz(e)){
            ans+=make(e[r].F-d,e[r].S);
            r++;
        }
        else{
            ans+=make(d-e[l].F,e[l].S);
            l--;
        }
    }
    return ans;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e.pb({c,{a,b}});
    }
    sort(all(e));
    // cout<<e[0].F<<" "<<e[1].F<<"\n";
    int q;
    cin>>q;
    while(q--){
        int d;
        cin>>d;
        cout<<solve(d)<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

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