oj.uz

답안 #984917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984917 2024-05-17T08:17:12 Z mnbvcxz123 시간이 돈 (balkan11_timeismoney) C++17
100 / 100
 350 ms 800 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;

// BeginCodeSnip{DSU}
struct DSU {
	vector<int> g;
	DSU(int n) : g(n, -1) {}
	int find(int a) { return g[a] < 0 ? a : (g[a] = find(g[a])); }
	/**
	 * If a and b are already in the same set, return false and do nothing.
	 * Otherwise, merge set a and b into one set and return true.
	 */
	bool unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return false;
		if (g[a] > g[b]) swap(a, b);
		g[a] += g[b];
		g[b] = a;
		return true;
	}
};
// EndCodeSnip

struct Edge {
	int x;
	int y;
	int time;
	int cost;
	int id;
};

/**
 * Kruskal's Algorithm to find a MST with given edges and weights. Returns the
 * time and cost as pair<int,int> as well as ids of edges of the MST as
 * vector<int>.
 */
pair<pii, vector<int>> kruskal(int n, vector<Edge> &edges,
                               vector<int> &weights) {
	sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2) {
		return weights[e1.id] < weights[e2.id];
	});
	DSU dsu(n);
	vector<int> mst;
	int t = 0;
	int c = 0;
	for (Edge &e : edges) {
		if (dsu.unite(e.x, e.y)) {
			t += e.time;
			c += e.cost;
			mst.push_back(e.id);
		}
	}
	return {{t, c}, mst};
}

/**
 * Calculate the signed area of the triangle defined by the given points.
 * This value is negative if point P is on the right side of vector AB.
 */
ll area(pii A, pii B, pii P) {
	pii AB = {B.first - A.first, B.second - A.second};
	pii AP = {P.first - A.first, P.second - A.second};
	return AB.first * AP.second - AB.second * AP.first;
}

int main() {
	int N, M;
	cin >> N >> M;

	vector<Edge> edges(M);
	for (int i = 0; i < M; i++) {
		int x, y, t, c;
		cin >> x >> y >> t >> c;
		edges[i] = {x, y, t, c, i};
	}

	// The best Minimum Spanning Tree found so far.
	vector<int> best_MST;
	// The sum of time and cost w.r.t. best_MST.
	pii best_V = {1e8, 1e8};
	vector<int> current_MST;
	pii A, B, P;
	// The weights used by Kruskal's Algorithm to determine the MST.
	vector<int> weights(M);

	// A corresponds to the values of the MST if we only minimize the time
	for (int i = 0; i < M; i++) { weights[edges[i].id] = edges[i].time; }
	tie(A, best_MST) = kruskal(N, edges, weights);
	best_V = A;

	// B corresponds to values of the MST if we only minimize the cost
	for (int i = 0; i < M; i++) { weights[edges[i].id] = edges[i].cost; }
	tie(B, current_MST) = kruskal(N, edges, weights);
	// If solution B is better than A, update the best solution
	if ((ll)B.first * B.second < (ll)A.first * A.second) {
		best_V = B;
		best_MST = current_MST;
	}

	// Search recursively for points on lower convex hull of the solution space
	stack<pair<pii, pii>> to_search;
	to_search.push({A, B});
	while (!to_search.empty()) {
		auto [A, B] = to_search.top();
		to_search.pop();

		/*
		 * Since P is on the right side of vector AB, the signed area is
		 * negative. Thus, to maximize the unsigned area of triangle ABP, we
		 * should minimize this signed value.
		 */
		for (int i = 0; i < M; i++) {
			weights[edges[i].id] = (edges[i].cost * (B.first - A.first) -
			                        edges[i].time * (B.second - A.second));
		}
		tie(P, current_MST) = kruskal(N, edges, weights);

		/*
		 * If P is on the left side of vector AB, we can terminate the search
		 * on this branch. Note that the "left side of vector AB" is the right
		 * side on the coordinate system.
		 */
		if (area(A, B, P) >= 0) { continue; }

		// Compare the V value and update the best result if needed.
		if ((ll)P.first * P.second < (ll)best_V.first * best_V.second) {
			best_V = P;
			best_MST = current_MST;
		}

		/*
		 * Search further with the new acquired point P to see if there is
		 * another point that is on a hyperbola further left than P.
		 */
		to_search.push({A, P});
		to_search.push({P, B});
	}

	cout << best_V.first << " " << best_V.second << "\n";
	sort(begin(edges), end(edges),
	     [](const Edge &e1, const Edge &e2) { return e1.id < e2.id; });
	for (int &id : best_MST) {
		cout << edges[id].x << " " << edges[id].y << "\n";
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 444 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 38 ms 488 KB Output is correct
17 Correct 47 ms 492 KB Output is correct
18 Correct 37 ms 488 KB Output is correct
19 Correct 350 ms 800 KB Output is correct
20 Correct 348 ms 760 KB Output is correct