제출 #737872

#제출 시각아이디문제언어결과실행 시간메모리
737872DeepessonReconstruction Project (JOI22_reconstruction)C++17
42 / 100
5056 ms282036 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 cur1,int cur2,ll custo,ll delta,int count,ll impacto,ll pos,std::vector<int>& novind,int& i){ if(count==N-1){ for(auto&x:partes){ ans[x.second]=custo+delta*(ll)x.first+impacto*(ll)abs((ll)pos-(ll)x.first); } return; } std::vector<pii> left,right; if(cur2<0){ left=partes; }else if(cur1<0) right=partes; else{ bool tranca=false; for(auto&x:partes){ if(cur1>=0&&(cur2<0||abs(con[novind[cur1]].first-x.first)<=abs(con[salva1[i][cur2]].first-x.first))){ left.push_back(x); tranca=true; }else { right.push_back(x); assert(!tranca); } } } if(left.size()){///Vai para a esquerda pip add = con[novind[cur1]]; ll 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(left,cur1-1,cur2,custo+bonusc,delta+bonusd,count+bonuscount,impacto+impcount,pos,novind,i); Undo(); } if(right.size()){ pip add = con[salva1[i][cur2]]; ll 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(right,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],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...