Submission #737888

#	Time	Username	Problem	Language	Result	Execution time	Memory
737888		Deepesson	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5095 ms	223556 KiB

reconstruction

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define MAX 505
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
int pai[MAX],size[MAX];
std::vector<pii> undo,undosz;
void limpa(void){
    for(int i=0;i!=MAX;++i){
        size[i]=1;
        pai[i]=i;
    }
    undo.clear();
    undosz.clear();
}
int find(int a){
    if(pai[a]==a)
        return a;
    return find(pai[a]);
}
void Undo(void){
    if(undo.back().first==-1){
        undo.pop_back();
    }else{
        pai[undo.back().first]=undo.back().second;
        size[undosz.back().first]=undosz.back().second;
        undo.pop_back();
        undosz.pop_back();
    }
}
bool Union(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b){
        if(size[a]>size[b])std::swap(a,b);
        undo.push_back({a,pai[a]});
        undosz.push_back({b,size[b]});
        pai[a]=b;
        size[b]+=size[a];
        return 1;
    }else undo.push_back({-1,-1});
    return 0;
}
std::vector<pip> con;
using ll = long long;
ll ans[1100000];
std::vector<pii> contratos;
int N,M,Q;
std::vector<int> salva1[105000];
std::vector<pii> queries[105000];
void Dnc(std::vector<pii>& partes,int L,int R,int cur1,int cur2,ll custo,ll delta,int count,ll impacto,ll pos,std::vector<int>& novind,int& i){
    if(L>R)return;
    if(count==N-1){
        for(int j=L;j<=R;++j){
            auto&x=partes[j];
            ans[x.second]=custo+delta*(ll)x.first+impacto*(ll)abs((ll)pos-(ll)x.first);
        }
        return;
    }
    ///O ultimo caracere eh quem ele se refere;
    int ll=-1,rl=-1,lr=-1,rr=-1;
    if(cur2<0){
        ll=L;
        rl=R;
    }else if(cur1<0){
        lr=L;
        rr=R;
    }else{
        int l=L,r=R;
        while(l<r){
            int m = (l+r)/2;
            if(abs(con[novind[cur1]].first-partes[m].first)<=abs(con[salva1[i][cur2]].first-partes[m].first)){
                r=m;
            }else l=m+1;
        }
        if(abs(con[novind[cur1]].first-partes[l].first)<=abs(con[salva1[i][cur2]].first-partes[l].first))
        {
            lr=L;
            rr=l-1;
            ll=l;
            rl=R;
        }else {
            lr=L;
            rr=R;
        }
    }
    if(ll!=-1){///Vai para a esquerda
        pip add = con[novind[cur1]];
        long long bonusc=0,bonusd=0,bonuscount=0,impcount=0;
        {
            int c = Union(add.second.first,add.second.second);
            if(c){
                ++bonuscount;
                if(add.first!=pos){
                    bonusc+=add.first;
                    bonusd-=1;
                }else ++impcount;
            }
        }
        Dnc(partes,ll,rl,cur1-1,cur2,custo+bonusc,delta+bonusd,count+bonuscount,impacto+impcount,pos,novind,i);
        Undo();
    }
    ///Vai para a direita
    if(rr!=-1){
        pip add = con[salva1[i][cur2]];
        long long bonusc=0,bonusd=0,bonuscount=0,impcount=0;
        {
            int c = Union(add.second.first,add.second.second);
            if(c){
                ++bonuscount;
                if(add.first!=pos){
                    bonusc-=add.first;
                    bonusd+=1;
                }else impcount++;
            }
        }
        Dnc(partes,lr,rr,cur1,cur2-1,custo+bonusc,delta+bonusd,count+bonuscount,impacto+impcount,pos,novind,i);
        Undo();
    }
}
void simula(void){
    std::vector<int> indices;
    for(int i=0;i!=M;++i){
        indices.push_back(i);
        int count=0;
        std::vector<int> novind;
        limpa();
        for(int j=indices.size()-1;j!=-1;--j){
            const int ref = indices[j];
            const int c = Union(con[ref].second.first,con[ref].second.second);
            if(c){
                ++count;
                novind.push_back(ref);
            }
        }
        std::reverse(novind.begin(),novind.end());
        indices=novind;
        salva1[i]=indices;
    }
    int cur=0;
    for(int i=0;i!=Q;++i){
        const pii ref = contratos[i];
        while((cur+1!=M)&&(abs(ref.first-con[cur].first)>=abs(ref.first-con[cur+1].first))){
            ++cur;
        }
        queries[cur].push_back(ref);
    }
    indices.clear();
    for(int i=M-1;i!=-1;--i){
        indices.push_back(i);
        int count=0;
        std::vector<int> novind;
        limpa();
        for(int j=indices.size()-1;j!=-1;--j){
            const int ref = indices[j];
            const int c = Union(con[ref].second.first,con[ref].second.second);
            if(c){
                ++count;
                novind.push_back(ref);
            }
        }
        std::reverse(novind.begin(),novind.end());
        indices=novind;
        std::sort(queries[i].begin(),queries[i].end());
        if(queries[i].size())
        {
            limpa();
            Dnc(queries[i],0,queries[i].size()-1,novind.size()-1,salva1[i].size()-1,0,0,0,0,con[i].first,novind,i);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>M;
    for(int i=0;i!=M;++i){
        int a,b,c;
        std::cin>>a>>b>>c;
        --a;--b;
        con.push_back({c,{a,b}});
    }
    std::sort(con.begin(),con.end());
    std::cin>>Q;
    for(int i=0;i!=Q;++i){
        int x;
        std::cin>>x;
        contratos.push_back({x,i});
    }
    std::sort(contratos.begin(),contratos.end());
    simula();
    for(int i=0;i!=Q;++i){
        std::cout<<ans[i]<<"\n";
    }
}

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