Submission #901637

#	Time	Username	Problem	Language	Result	Execution time	Memory
901637		alexander707070	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1460 ms	68412 KiB

reconstruction

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const int inf=1e9;

struct edge{
    int from,to,cost;
};

int n,m,a,b,c,pt,q,pos,l,r,mid,lt,rt;
int dsu[MAXN],sz[MAXN];
int mins[MAXN],maxs[MAXN];
long long incr[MAXN],sum,ans[MAXN],mult[MAXN],t,x[MAXN];
edge e[MAXN];

bool cmp(edge fr,edge sc){
    return fr.cost<sc.cost;
}

void reset_dsu(){
    for(int i=1;i<=n;i++){
        dsu[i]=i; sz[i]=1;
    }
}

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    int rootx=root(x);
    int rooty=root(y);

    if(rootx==rooty)return;
    if(sz[rootx]<sz[rooty])swap(rootx,rooty);

    dsu[rooty]=rootx;
    sz[rootx]+=sz[rooty];
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        e[i]={a,b,c};
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>x[i];
    }

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=m;i++){
        reset_dsu();

        pos=0; mins[i]=0;
        for(int f=i-1;f>=1;f--){
            mergev(e[f].from,e[f].to);
            if(root(e[i].from)==root(e[i].to)){
                pos=f; break;
            }
        }

        if(pos!=0){
            mins[i]=(e[pos].cost+e[i].cost)/2;

            if((e[pos].cost+e[i].cost)%2==1){
                mins[i]++;
            }
        }

        reset_dsu();

        pos=m+1; maxs[i]=inf;
        for(int f=i+1;f<=m;f++){
            mergev(e[f].from,e[f].to);
            if(root(e[i].from)==root(e[i].to)){
                pos=f; break;
            }
        }

        if(pos!=m+1){
            maxs[i]=(e[pos].cost+e[i].cost)/2;
            if((e[pos].cost+e[i].cost)%2==0){
                maxs[i]--;
            }
        }
    }

    for(int i=1;i<=m;i++){
        l=0; r=q+1;

        while(l+1<r){
            mid=(l+r)/2;
            if(x[mid]>=mins[i]){
                r=mid;
            }else{
                l=mid;
            }
        }

        lt=r;

        l=0; r=q+1;

        while(l+1<r){
            mid=(l+r)/2;
            if(x[mid]<=maxs[i]){
                l=mid;
            }else{
                r=mid;
            }
        }

        rt=l;

        l=0; r=q+1;

        while(l+1<r){
            mid=(l+r)/2;
            if(x[mid]<=e[i].cost){
                l=mid;
            }else{
                r=mid;
            }
        }

        if(lt>rt)continue;

        incr[lt]+=e[i].cost;
        mult[lt]--;

        incr[l+1]+=-2*e[i].cost;
        mult[l+1]+=2;

        incr[rt+1]+=e[i].cost;
        mult[rt+1]--;
    }

    for(int i=1;i<=q;i++){
        sum+=incr[i]; 
        t+=mult[i];
        ans[i]=sum+t*x[i];
    }

    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }

    return 0;
}

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