답안 #624088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624088 2022-08-07T08:30:39 Z chuangsheep 시간이 돈 (balkan11_timeismoney) C++11
100 / 100
408 ms 668 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;

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

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;
	}
};

/**
 * 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";
	}
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:109:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |   auto [A, B] = to_search.top();
      |        ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 220 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 10 ms 612 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 4 ms 212 KB Output is correct
15 Correct 3 ms 212 KB Output is correct
16 Correct 46 ms 364 KB Output is correct
17 Correct 49 ms 344 KB Output is correct
18 Correct 46 ms 340 KB Output is correct
19 Correct 399 ms 668 KB Output is correct
20 Correct 408 ms 668 KB Output is correct