Submission #1064087

#TimeUsernameProblemLanguageResultExecution timeMemory
1064087WarinchaiReconstruction Project (JOI22_reconstruction)C++14
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> #define int long long using namespace std; vector<pair<int,pair<int,int>>>edge; vector<int>qr; vector<int>ans; vector<int>order; vector<int>rorder; int p[505]; int n,m; int fp(int a){return p[a]==a?a:p[a]=fp(p[a]);} void un(int a,int b){p[fp(b)]=fp(a);} pair<pair<int,int>,pair<int,int>> get_res(int x,int r){ //cerr<<"x:"<<x<<"\n"; int l=r-1; int ansl=0,ansr=0,fl=0,fr=0; while(l>=0&&r<m){ while(l>=0&&(fp(edge[l].second.first)==fp(edge[l].second.second)))l--; while(r<m&&(fp(edge[r].second.first)==fp(edge[r].second.second)))r++; if(l<0||r>=m)break; if(abs(x-edge[l].first)<abs(x-edge[r].first))/*cerr<<edge[l].second.first<<" "<<edge[l].second.second<<" "<<abs(x-edge[l].first)<<"\n",*/un(edge[l].second.first,edge[l].second.second),ansl+=abs(x-edge[l].first),fl++,l--; else /*cerr<<edge[r].second.first<<" "<<edge[r].second.second<<" "<<abs(x-edge[r].first)<<"\n",*/un(edge[r].second.first,edge[r].second.second),ansr+=abs(x-edge[r].first),fr++,r++; } while(l>=0){ if(fp(edge[l].second.first)!=fp(edge[l].second.second))/*cerr<<edge[l].second.first<<" "<<edge[l].second.second<<" "<<abs(x-edge[l].first)<<"\n",*/un(edge[l].second.first,edge[l].second.second),ansl+=abs(x-edge[l].first),fl++; l--; } while(r<m){ if(fp(edge[r].second.first)!=fp(edge[r].second.second))/*cerr<<edge[r].second.first<<" "<<edge[r].second.second<<" "<<abs(x-edge[r].first)<<"\n",*/un(edge[r].second.first,edge[r].second.second),ansr+=abs(x-edge[r].first),fr++; r++; } return {{ansl,fl},{ansr,fr}}; } vector<int>v; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=0;i<m;i++){ int a,b,w;cin>>a>>b>>w; edge.push_back({w,{a,b}}); order.push_back(w); } sort(edge.begin(),edge.end()); sort(order.begin(),order.end()); order.erase(unique(order.begin(),order.end()),order.end()); int q;cin>>q; for(int i=0;i<q;i++){ int x;cin>>x; qr.push_back(x); } int pr=-1; pair<pair<int,int>,pair<int,int>>res; int ans=0; int id=0; int val=0; for(auto x:qr){ while(id<m&&edge[id].first<x)id++; //cerr<<"id:"<<id<<"\n"; if(id!=pr){ for(int i=1;i<=n;i++)p[i]=i; res=get_res(x,id); ans=res.first.first+res.second.first; val=x; }else{ ans=res.first.first+res.first.second*(x-val)+res.second.first-res.second.second*(x-val); } pr=id; //cerr<<"ans:"<<res.first.first<<" "<<res.first.second<<" "<<res.second.first<<" "<<res.second.second<<"\n"; cout<<ans<<"\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...