제출 #1131257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131257		idiotcomputer	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	724 ms	676 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()

const int mxM = 1e4+5;
const int mxN = 205;
int n,m;
ll res = 1e16;
pii val;

pii v[mxM];
pii e[mxM];
int cost[mxM];

//DSU
int p[mxN];
int ss[mxN];
int getp(int a){
	if (p[a] == a) return a;
	p[a] = getp(p[a]);
	return p[a];
}

void join(int a, int b){
	a = getp(a);
	b = getp(b);
	if (a == b) return;
	if (ss[a] < ss[b]) swap(a,b);
	p[b] = a;
	ss[a] += ss[b];
}

bool comp(int a, int b){
	return cost[a] < cost[b];
}

vector<int> edges;
pii mst(){
	vector<int> all(m);
	for (int i = 0; i < m; i++) all[i] = i;
	for (int i = 0; i < n; i++) p[i] = i, ss[i] = 1;

	sort(all.begin(),all.end(),comp);
	pii tot = {0,0};
	edges.clear();
	for (int i = 0; i < m; i++){
		int c = all[i];
		if (getp(e[c].f) == getp(e[c].s)) continue;
		join(e[c].f,e[c].s);
		tot.f += v[c].f;
		tot.s += v[c].s;
		edges.pb(c);
		if (sz(edges) >= n-1) break;
	}
	return tot;
}

void dc(pii a, pii b){
	if (b.f < a.f) swap(a,b);
	//cout << "Dc" << ": " << a.f << ',' << a.s << " " << b.f << ',' << b.s << "\n";
	for (int i = 0; i < m; i++) cost[i] = v[i].f * (a.s - b.s) + v[i].s * (b.f - a.f);
	pii c = mst();
	if ((a.f-b.f) * (a.s-c.s) >= (a.s-b.s) * (a.f-c.f)) return;
	if ((ll) c.f * (ll) c.s < res){
		res = (ll) c.f * (ll) c.s;
		val = {(a.s - b.s),(b.f - a.f)};
	}
	dc(a,c);
	dc(c,b);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;

	for (int i = 0; i < m; i++){
		cin >> e[i].f >> e[i].s >> v[i].f >> v[i].s;
	}

	for (int i = 0; i < m; i++) cost[i] = v[i].f;
	pii A = mst();
	for (int i = 0; i < m; i++) cost[i] = v[i].s;
	pii B = mst();
	dc(A,B);
	if ((ll) A.f * (ll) A.s < res){
		res = (ll) A.f * (ll) A.s;
		val = {1,0};
	}
	if ((ll) B.f * (ll) B.s < res){
		res = (ll) B.f * (ll) B.s;
		val = {0,1};
	}

	for (int i = 0; i < m; i++) cost[i] = v[i].f * val.f + v[i].s * val.s;
	pii temp = mst();
	cout << temp.f << " " << temp.s << '\n';
	for (int i = 0; i < n-1; i++) cout << e[edges[i]].f << " " << e[edges[i]].s << "\n";

//	cout << res << '\n';
	return 0;
}

• Subtask 1: 100 / 100