#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename key>
// for ordered set or indexed set
using ordered_set= tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; // less_equal
#define f1(n) for(int i=0;i<n;i++)
#define e '\n'
#define f2(m,n,q) for(int i=m;i<n;i+=q)
#define f3(n) for(int j=0;j<n;j++)
#define f4(m,n,q) for(int j=m;j<n;j+=q)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define pb push_back
//f^=1 == if(f==0)f=1 else f=0
typedef long long ll;
const int N=205;
const int mod=1e9+7;
const int inf=1e9,sqr=448;
vector<int>v[N];int mn[N],mx[N];
struct DSU{
vector<int>parent,sz;int nm;
void init(int n){
parent.resize(n+1);sz.resize(n+1,1);
f2(1,n+1,1)parent[i]=i,mx[i]=i,mn[i]=i;
nm=n;
}
int root(int u){
if(parent[u]==u)return u;
return root(parent[u]);
}
bool merge(int u,int v){
int ru=root(u),rv=root(v);
if(ru==rv)return 0;
if(sz[ru]>sz[rv])swap(ru,rv);
parent[ru]=rv;sz[rv]+=sz[ru];
mn[rv]=min({mn[rv],u,v,mn[ru]});mx[rv]=max({mx[rv],u,v,mx[ru]});
nm--;
return 1;
}
int siz(int u){return sz[root(u)];}
};
int32_t main()
{
speed;
int tt=1,cnt=0;//cin>>tt;
while(tt--){
//freopen("herding.in","r",stdin);
//freopen("herding.out","w",stdout);
int n,m;cin>>n>>m;
DSU d;d.init(n);
if(m==n-1){
int sm=0,sm1=0;vector<array<int,3>>v(m+1);vector<array<int,2>>p;
f2(1,m+1,1){
int x;
cin>>v[i][1]>>v[i][2]>>v[i][0]>>x;
p.pb({v[i][1],v[i][2]});sm+=v[i][0];sm1+=x;
}
cout<<sm<<' '<<sm1<<e;
for(auto it:p)cout<<it[0]<<' '<<it[1]<<e;
}
int sm=0;vector<array<int,3>>v(m+1);vector<array<int,2>>p;
f2(1,m+1,1){
int x;
cin>>v[i][1]>>v[i][2]>>v[i][0]>>x;
}
sort(v.begin(),v.end());
for(auto it:v){
if(d.root(it[1]+1)!=d.root(it[2]+1)){
d.merge(it[1]+1,it[2]+1);
p.pb({it[1],it[2]});
sm+=it[0];
}
}
cout<<sm<<' '<<sm<<e;
for(auto it:p)cout<<it[0]<<' '<<it[1]<<e;
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
