//#include <bits/stdc++.h>
#include <random>
#include "set"
#include <iostream>
/*
====================================================================================================
#*###*############*####*#####*####*############*#########################################*##########
%%%%%%%%%###%##*##=*+++=+++++++++++++*@#@%%###%%%%%%%%%%%%%%%%%%%%@%@@@%@@@@@@@@@@@@@%%%%%%%@@@%%%%#
%%%%%%%%%%#####*##=*++++++++++++++++=*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%@@@@@@@@%%%@@%%@@@%%%%#
%%%%%%%%%######*##=*+++++++++++++++++*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%@@@@@@@@@%%#%%%%@@%#%#%#
%%%%%%%%%%%####*##=*++++++++++++++++=+@%@%%###%@@@%%%%%%%%%%%%%%%%%%%%%%%@@%%%%@@@@@%%@%%%%%@%%%####
%%%%%%%%%%####%*##=*++++++++++++++++=+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@%@@@%%%%%@%######
%%%%%%%%%%####%*##=*++++++++++++++===+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%@@@@%#@%%%%%%@%#######
%%%%%%%%%%#####*##+++++++++++=++++=+++@%#%##%#######%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@#%%%%%%@########
%%%%%%%%%%#####*##+*+++++++++++++++==@%%%%%@##:-%=-=-+@%%%%%%%%%%%%%%%%%%%%%%%@@%%%@@@%%%%%@%%######
%%%%%%%%%%#####*##+*++++++++++++=+*%%%%%%%%#%*.@:-%+-++%%%%%%%%%%%%%%%%%%%@%%%@%%%%%%%%%%%@@%#######
%%%%%%%%%%####%*##=*=++++++++++++@%%%%%%%%%%%%#@@@@@@@=-@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@#######
%%%%%%%%%%####%*##+*++++++++++++%@%%@%%%%%%%%#%@###*#%%@@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
%%%%%%%%%%####%*##+*+++++++++==@@%@@@@%%@%###%#@#=%@@@@@@@#=+@%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
%%%%%%%%%%####%*##*++++++++++++@@@@@@%#%%%%@#@@@@@@@@@@@@@@@@@-#%%%%%%%%%%%%%%@%%%%%%%%%%@@@%%%#####
%%%%%%%%%#########=*++++++++++@@@@@%#@@@%%@@@@@@@@@@@@@@@@@@@@%@%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%#####
%%%%%%%%######%*##=*++++++++++@%%@@@@@@@@@%%%####%@@%%%%@@@@@@@%#%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%#####
%%%%%%%%##########=*++++++***#%%@@@@@@%%##*++++++***#*++*#%@@@@%%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%####
%%%%%%%%######%###=*++++++#@%%@%@@@@%#*+++++====++++++++++*#@@@@%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%###
%%%%%%%%######%###=*++++*%%%%@@@@@@@#+++++++=========++++++*#@@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%####
%%%%%%%%%#####%###=*++**%@#@@@@@@@@%+++=================++++*@@@@%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%#########=*+*#*@%@@@@@@%@%*++*+**##*++======*####*#*%@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
%%%%%%%%%%########=#+*@%@@@@@@%@@@#*+=-=****#*+=+++=**#**#*+*#%@@%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###
%%%%%%%%%%########+#*#@@@@%%%@@@%%#*+++*+=##+#*+*++##*+%**#**#%@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%%########=#**@@@@@@@@@@@@#*+=+=+++++++*==+*#*****++*#%%@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
%%%%%%%%%#########=#**@@@@@@@@@@@@#*+===++++==+=+++**++=++++#%@@@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%#####%###=##%@@@@@@@@@@@@#**+========++====++==+++*#%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##
%%%%%%%#%#########+#+%@%#@@@@@@@@@%**+========+++===*++++++#%@@@%@%%%%%%%%@%%%%@%%%%%%%%%%%%%%%%####
%%%%%%%%%%%#######=#+@@@@@@@@@@@@@#**++===+++****#**##*+++*%%@@@@@@%%%%@@@@@@@@@@@%%%%%%%%%%%%%%####
@%%%%%##%%########+***@@@@@@@@@@@%#***++++*****#%###%%****#%@@@@%@%%%%%%%%%%%%%%%%%%%%%%%%#%%%%%%@@@
%%%%%%%#%##%%%%###+**##%#@@@@@@@###***+++++++++++++*******#@@@@@@%%#%%%%%%%%%%%@%%%%%%%%%%%%%%%%%##%
#@##%%##%##%######+**+++*@%##%%%%*********+++++++**********@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##%
%@##%#%%%####%####+#*+*+++++++++#%**************************#%#*#%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%#%%%#
@%%###%#%########*++===========++#@*++******##########******#++======@%%%%%%%%@%%%%%%%%%%%%%%%%%#%%#
%%%##%##%##%###*++=========+=++++++*#********######*******+*=+==--=====*%%%#%%@%%%%%%%%%%%%%%%@%%%%#
%%%##%%#%#####+++++*+=========+==+++**#******#####*******+*+++++==:======*%#%%@%%%%%%%%%%%%%%%%%%%#%
%%%##%%%%#++==========--=----====+++++*##*****###*****+++#*===--+=====-------+**#@@%%%%%%%%%%%%%%%%%
%#%%%+*++==========-=--=---------========++*@********+=%#===========----------======+@%%%%%%%%%%%%%%
%#%***++========----------------------======++@.+++++*+==========---------------=-=====@%%%%%%%%%%%%
%%**+++=========------------=---------=======+++*+*+%++========------------------==-====%%%%%%%%%%%%
%**++++=========--===-=--=======------===========#*++============---------====----======+*%%%%%%%%%%
#**+++++====+============+++++========-===========+*==============--=====+++++=====+===+=+*%%%%%%%%%
#****+++==++++=====++++++****+++++===--=========+++++++=================+++***+++++++++++++%%%%%%%%%
#*****+++++++++++++++++***##***++===-=---=======++*=*++++==============++++**#***+++++++++*+%%%%%%%%
#******++++***++++++***######*+=====-----=--====++*+**+++======-=--=======+*#*##***+*+****#+@@%%%%%%
##********+**********####%%%+++++=====-----=====++*+***+++================++*#%####*********%@%+%%%%
###***************######%%#**++++++=============++++*#*+++======-========++++*%%####******#*%@@%%%%%
####****************##%%@#***++++++++++=========+++*=**++==============++++++**%%###*********#%%*%%%
*****************+====*%%*********+++++===+====+++++++**++==+=*=====+++++++****@##++++=+****++*@%%%%
*************+++=====--=@************+++++++++++++++******+++++++++++++++******#*+=====+++++*+++@%%%
***+++++*++++++=========+########**#%%*******++******%##***+++*++++++++++*******++++====++=++++**%%%
***+++========++========+%######*%###%#**************%###***************########***++++++++++++**#%%
***+++++++=====+++====+++*@#####%%%%%%######********#######**********###%%%%##%#**#*+++++==+++++**%%
***++++++++=======++++++**@%#######################%*#%%%#################%%#%%##**#*+++++++++++***%
***+++++**+++==========+*+#%%#######################**#%%###################%@%###*##*++++*+++++***%
****+**+++++++=======++*#*#@%%%%%%%%###########%%%#*****##%#%###########%%%%@%%%######+++++++++++***
#*****+++++++++=====+++***#%%%%%%%%%%%%%%%%%%%%%%**++===+*#%%%%%%%%%%%%%%%%%@@%%#######*++++===+++**
#*****+++++++=======+++**#%%%%%%%##############*+++==-===++*####%%%%%%##%%%%@@%%%######**+=====+++**
##****+++++++=====+*++***#%%%%%%%###########***++++++++++=++**############%%%%%%%%####****#*+=++++**
====================================================================================================
*/
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
#define _ << ' ' <<
#define clearvis for (int i=0; i<maxn;visited[i++]=false)
//__int128 fpow(ll base,ll exp){__int128 result=1;while (exp){if (exp%2==1) result*=base;exp/=2;base*=base;}return result;}
ll fastpow(ll base, ll exp) {
ll res = 1;
while (exp) {
if (exp & 1)
res *= base;
base *= base;
res %= MOD;
base %= MOD;
exp >>= 1;
}
return res;
}
struct edge{
ll u,v,t,c;
};
ll st=0,sc=0;
bool cmp(edge x, edge y){
if (st == 0) return x.t*x.c < y.t*y.c;
return (st+x.t)*(sc+x.c) < (st+y.t)*(sc+y.c);
}
const ll maxn = 205;
const ll maxm = 2e4;
edge arr[maxm];
// Abdulrahman Alghamdi (ibsha)
ll parent[maxn], Size[maxn]; // CHANGE THIS VALUE depending on the task, do NOT forget
ll comps = 0, maxcomp = 1;
void make_set(ll v) { // make a component with only v
return (void)(parent[v] = v, Size[v] = 1, comps++);
}
ll find(ll v) { // finds the ancestor of v, useful for knowing component size. Size[find(node)]
if (v == parent[v]) return v;
return parent[v] = find(parent[v]);
}
void merge(ll a, ll b) { // merges 2 sets (simple, right?)
a = find(a), b = find(b);
if (a != b) {
comps--;
if (Size[a] < Size[b]) swap(a,b);
parent[b] = a;
Size[a] += Size[b];
maxcomp = max(maxcomp, Size[a]);
}
}
void solve() {
// cout << fixed << setprecision(6);
ll n,m; cin >> n >> m;
for (int i=0;i<m;i++){
ll u,v,t,c;
cin >> u >> v >> t >> c;
arr[i] = {u,v,t,c};
}
sort(arr,arr+m,cmp);
for (int i = 0; i < n; i++){
make_set(i);
}
vector<pll> edges;
while(1){
sort(arr,arr+m,cmp);
ll i = 0;
auto [u,v,t,c] = arr[i];
if (find(u) == find(v)) continue;
st+=t;
sc+=c;
merge(u,v);
edges.push_back({u,v});
arr[i].t = 300;
arr[i].c = 300;
if (comps == 1) break;
}
cout << st _ sc << endl;
for (auto [x,y] : edges) cout << x _ y << endl;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
//freopen("berries.in","r",stdin);
//freopen("berries.out","w",stdout);
ll t=1;
//cin >> t;
for (int i=1; i<=t; i++){
//cout << "Case #" << i << ": ";
solve();
cout << endl;
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
