Submission #967630

#	Time	Username	Problem	Language	Result	Execution time	Memory
967630		sano	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1349 ms	2416 KiB

timeismoney

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<unordered_map>
#include <set>
#define ll long long
#define For(i, n) for(ll i = 0; i < n; i++)
#define ffor(i, a, n) for(ll i = a; i < n; i++)
#define rfor(i, n) for(ll i = n; i >= 0; i--)
#define rffor(i, a, n) for(ll i = n; i >= a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1e18
#define mod (1e9 + 7)
#define rsz resize
#define prv 47
using namespace std;

ll mini = NEK;
ll minit = 1000000000;
ll minic = 1000000000;
vec<ll> odp;
vec<ll> odp_lok;
ll n;

struct hrana{
	ll x, y, t, c;
};

vec<hrana> h_pov;

struct tr {
	ll x, y, w, ind;
};

bool zorad(tr a, tr b) {
	return a.w < b.w;
}

ll otec(ll x, vec<ll>&o) {
	if (o[x] == x) return x;
	return o[x] = otec(o[x], o);
}

pii kruskal(ll k1, ll k2) {
	vec<ll> o(n);
	For(i, n) o[i] = i;
	vec<tr> h;
	ll m = h_pov.size();
	For(i, m) {
		h.push_back({ h_pov[i].x, h_pov[i].y, h_pov[i].c * k2 - h_pov[i].t * k1, i });
	}
	sort(h.begin(), h.end(), zorad);
	ll val = 0;
	ll suc_t = 0;
	ll suc_c = 0;
	For(i, m) {
		if (otec(h[i].x, o) == otec(h[i].y, o)) continue;
		val += h[i].w;
		suc_t += h_pov[h[i].ind].t;
		suc_c += h_pov[h[i].ind].c;
		o[otec(h[i].x, o)] = otec(h[i].y, o);
		odp_lok.push_back(h[i].ind);
	}
	return { suc_t, suc_c };
}

void divide(pii a, pii b) {
	ll k1 = b.ss - a.ss;
	ll k2 = b.ff - a.ff;
	pii c = kruskal(k1, k2);
	if (((b.ff - a.ff) * (c.ss - a.ss) - (b.ss - a.ss) * (c.ff - a.ff)) > 0 || ((c.ff == a.ff) && (c.ss == a.ss)) || ((c.ff == b.ff) && (c.ss == b.ss))) {
		odp_lok.clear();
		return;
	}
	if (mini > c.ff * c.ss) {
		mini = c.ff * c.ss;
		minit = c.ff;
		minic = c.ss;
		odp.clear();
		for (auto i : odp_lok) odp.push_back(i);
	}
	odp_lok.clear();
	divide(a, c);
	divide(c, b);
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin("curling.in");
	//ofstream cout("curling.out");
	cin >> n;
	ll m;
	cin >> m;
	For(i, m) {
		ll x, y, t, c;
		cin >> x >> y >> t >> c;
		h_pov.push_back({ x, y, t, c });
	}
	pii a = kruskal(-1, 0);
	if (mini > a.ff * a.ss) {
		mini = a.ff * a.ss;
		minit = a.ff;
		minic = a.ss;
		odp.clear();
		for (auto i : odp_lok) odp.push_back(i);
	}
	odp_lok.clear(); 
	pii b = kruskal(0, 1);
	if (mini > b.ff * b.ss) {
		mini = b.ff * b.ss;
		minit = b.ff;
		minic = b.ss;
		odp.clear();
		for (auto i : odp_lok) odp.push_back(i);
	}
	odp_lok.clear();
	divide(a, b);
	cout << minit << ' ' << minic << '\n';
	for (auto i : odp) cout << h_pov[i].x << ' ' << h_pov[i].y << '\n';
	return 0;
}

• Subtask 1: 100 / 100