제출 #737879

#제출 시각아이디문제언어결과실행 시간메모리
737879DeepessonReconstruction Project (JOI22_reconstruction)C++17
0 / 100
5056 ms223604 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{ int l=0,r=partes.size()-1; while(l<r){ int m = (l+r+1)/2; if(abs(con[novind[cur1]].first-partes[m].first)<=abs(con[salva1[i][cur2]].first-partes[m].first)){ l=m; }else r=m-1; } if(abs(con[novind[cur1]].first-partes[l].first)<=abs(con[salva1[i][cur2]].first-partes[l].first)) { for(int j=0;j<l;++j){ right.push_back(partes[j]); } for(int j=l;j<partes.size();++j){ left.push_back(partes[j]); } }else right=partes; } 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"; } }

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'void Dnc(std::vector<std::pair<int, int> >&, int, int, ll, ll, int, ll, ll, std::vector<int>&, int&)':
reconstruction.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int j=l;j<partes.size();++j){
      |                         ~^~~~~~~~~~~~~~
#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...