# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1010757 | vjudge1 | timeismoney (balkan11_timeismoney) | C++11 | 4 ms | 988 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
long long n,m,ai,bi,ti,ci,sum;
int par[201],rnk[201];
vector<pair<int,int> >v[201];
vector<pair<long long,pair<int,int> > >edging;
vector<pair<int,int> >answer;
int get(int x){
if(par[x]==x)return x;
return par[x]=get(par[x]);
}
void combine(int x,int y){
x=get(x);
y=get(y);
if(x!=y){
if(rnk[x]<rnk[y])swap(x,y);
par[x]=y;
if(rnk[x]==rnk[y])rnk[x]++;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)par[i]=i;
for(int i=0;i<m;i++){
cin>>ai>>bi>>ti>>ci;
v[ai].push_back({bi,ci});
v[bi].push_back({ai,ci});
edging.push_back({ci,{ai,bi}});
}
sort(edging.begin(),edging.end());
for(int i=0;i<m;i++){
long long ci=edging[i].first;
int ai=edging[i].second.first;
int bi=edging[i].second.second;
if(get(ai)!=get(bi)){
answer.push_back({edging[i].second.first,edging[i].second.second});
sum+=ci;
combine(ai,bi);
}
}
cout<<sum<<' '<<sum<<'\n';
for(int i=0;i<answer.size();i++)cout<<answer[i].first<<' '<<answer[i].second<<'\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |