#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)/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))
{
for(int j=0;j<l;++j){
left.push_back(partes[j]);
}
for(int j=l;j<partes.size();++j){
right.push_back(partes[j]);
}
}else left=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";
}
}
Compilation message
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){
| ~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5252 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5252 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Execution timed out |
5074 ms |
225272 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5252 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5252 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5252 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
