제출 #737887

#제출 시각아이디문제언어결과실행 시간메모리
737887DeepessonReconstruction Project (JOI22_reconstruction)C++17
42 / 100
5065 ms223576 KiB
#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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...