답안 #967630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967630 2024-04-22T14:24:39 Z sano 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
1349 ms 2416 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 7 ms 1568 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 8 ms 516 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 134 ms 660 KB Output is correct
17 Correct 136 ms 660 KB Output is correct
18 Correct 127 ms 600 KB Output is correct
19 Correct 1326 ms 1880 KB Output is correct
20 Correct 1349 ms 2416 KB Output is correct