Submission #884897

#	Time	Username	Problem	Language	Result	Execution time	Memory
884897		amirhoseinfar1385	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	427 ms	36556 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
const long long maxn=505,maxm=100000+10;
struct yal{
    long long u,v,w,ind;
    bool operator <(const yal a)const{
        if(a.w!=w){
            return w<a.w;
        }
        if(a.u!=u){
            return u<a.u;
        }
        return v<a.v;
    }
};
struct updy{
    long long l,val,ted;
    updy(long long a=0,long long b=0,long long c=0){
        l=a;
        val=b;
        ted=c;
    }
    bool operator <(const updy a)const{
        if(a.l!=l){
            return l<a.l;
        }
        if(a.val!=val){
            return val<a.val;
        }
        return ted<a.ted;
    }
}fupdy;
struct dsu{
    long long par[maxn],sz[maxn];
    void clear(){
        memset(par,0,sizeof(par));
        memset(sz,0,sizeof(sz));
    }
    long long root(long long u){
        if(par[u]==0){
            return u;
        }
        return par[u]=root(par[u]);
    }
    long long con(long long u,long long v){
        u=root(u),v=root(v);
        if(u!=v){
            if(sz[u]<sz[v]){
                swap(u,v);
            }
            par[v]=u;
            sz[u]+=sz[v]+1;
            return 1;
        }
        return 0;
    }
}ds;
vector<updy>allq;
vector<yal>alle,v;
long long n,m;

long long upd(){
    ds.clear();
    for(long long i=(long long)v.size()-1;i>=0;i--){
       // cout<<"ha: "<<v[i].u<<" "<<v[i].v<<" "<<v[i].ind<<"\n";
        if(ds.con(v[i].u,v[i].v)==0){
         //   cout<<"nababa"<<endl;
            long long ret=v[i].ind;
            v.erase(v.begin()+i);
            return ret;
        }
    }
    return -1;   
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    alle.resize(m);
    for(long long i=0;i<m;i++){
        cin>>alle[i].u>>alle[i].v>>alle[i].w;
        allq.push_back(updy(alle[i].w,-2*alle[i].w,2));
    }
    sort(alle.begin(),alle.end());
    for(long long i=0;i<m;i++){
        alle[i].ind=i;
    }
    for(long long i=0;i<m;i++){
        v.push_back(alle[i]);
        long long ind=upd();
        if(ind==-1){
            allq.push_back(updy(-1,alle[i].w,-1));    
        }
        else{
            long long rl=(alle[i].w+alle[ind].w+1)/2;
           // cout<<i<<" "<<ind<<" "<<alle[i].w<<" "<<alle[ind].w<<" wtf"<<endl;
            allq.push_back(updy(rl,alle[i].w,-1));
            allq.push_back(updy(rl,alle[ind].w,-1));
        }
    }
    sort(allq.rbegin(),allq.rend());
    long long q;
    cin>>q;
    long long res=0,ted=0;
    for(long long i=0;i<q;i++){
        long long d;
        cin>>d;
        while((long long)allq.size()>0&&allq.back().l<=d){
            auto x=allq.back();
            allq.pop_back();
            res+=x.val;
            ted+=x.ted;
            //cout<<"outy: "<<x.val<<" "<<x.ted<<" "<<x.l<<" "<<d<<"\n";
        }
        long long mainres=res+d*ted;
        cout<<mainres<<"\n";
    }
}

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