oj.uz

답안 #385512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385512 2021-04-04T14:08:19 Z LucaDantas 시간이 돈 (balkan11_timeismoney) C++17
100 / 100
 553 ms 748 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

constexpr int maxn = 210, maxm = 1e4+10;

int n, m;

struct DSU
{
	int pai[maxn], peso[maxn];
	bool get_ans = 0;
	void init() { for(int i = 0; i <= n; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	bool join(int a, int b) {
		int x = a, y = b;
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(peso[a] < peso[b])
			swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
		if(get_ans) printf("%d %d\n", x, y);
		return 1;
	}
} dsu;


struct Edge
{
	int a, b, t, c;
} edges[maxm];

long long val(Edge x, int A, int B) { 
	return 1ll * x.t * A + 1ll * x.c * B;
}

pair<int,int> get(int A, int B) {
	// printf("%d %d\n", A, B);
	dsu.init();
	pair<int,int> ans = {0, 0};
	sort(edges, edges+m, [A, B](Edge x, Edge y) {
		if(val(x, A, B) == val(y, A, B)) return x.t < y.t;
		return val(x, A, B) < val(y, A, B);
	});
	for(int i = 0; i < m; i++)
		if(dsu.join(edges[i].a, edges[i].b))
			ans.first += edges[i].t, ans.second += edges[i].c;
	return ans;
}

struct ANS {
	long long v; int t, c, A, B;
	ANS() : v() {}
	ANS(int T, int C, int a, int b) {
		v = 1ll*T*C, t = T, c = C, A = a, B = b;
	}
} ans;

ANS min(ANS a, ANS b) {
	if(a.v < b.v) return a;
	return b;
}

using pii = pair<int,int>;
bool cross(pii a, pii b, pii c) {
	b.first -= a.first;
	c.first -= a.first;
	b.second -= a.second;
	c.second -= a.second;
	return (1ll * b.first * c.second - 1ll * b.second * c.first) != 0ll;
}

void solve(pii l, pii r) {
	// we want to find the vector parallel to the line between l and r
	// because the point that minimizes the dot with such vector is
	// the 'furthest point' in the direction of that line

	// we can find such vector by taking the slope of the line and
	// using the standard formula to calculate the slope of the parelell
	// line.


	int x = r.first - l.first, y = r.second - l.second;
	pii m = get(-y, x); // keep things positive for simplicity
	
	ans = min(ans, ANS(m.first, m.second, -y, x));
	if(cross(l, m, r)) {
		solve(l, m);
		solve(m, r);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int a, b, t, c; scanf("%d %d %d %d", &a, &b, &t, &c);
		edges[i] = {a, b, t, c};
	}
	pair<int,int> l = get(1, 0);
	pair<int,int> r = get(0, 1);
	ans = min(ANS(l.first, l.second, 1, 0), ANS(r.first, r.second, 0, 1));
	solve(l, r);
	dsu.get_ans = 1;
	printf("%d %d\n", ans.t, ans.c);
	get(ans.A, ans.B);
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:98:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   int a, b, t, c; scanf("%d %d %d %d", &a, &b, &t, &c);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 5 ms 364 KB Output is correct
15 Correct 4 ms 364 KB Output is correct
16 Correct 59 ms 364 KB Output is correct
17 Correct 65 ms 364 KB Output is correct
18 Correct 59 ms 364 KB Output is correct
19 Correct 536 ms 620 KB Output is correct
20 Correct 553 ms 748 KB Output is correct