oj.uz

답안 #1009691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009691 2024-06-27T20:24:37 Z Ivo_12 시간이 돈 (balkan11_timeismoney) C++
0 / 100
 837 ms 860 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair < ll, ll >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
struct Edge {
	ll a, b, t, m;
};
 
const ll N = 1e3+10, M = 1e5+10;
ll n, m;
Edge edges[M];
ll x, y;
 
ll par[N];
ll sz[N];
 
int fn( int i ) {
	if(par[i] == i) return i;
	return par[i] = fn(par[i]);
}
 
void un( int a, int b ) {
	a = fn(a); b = fn(b);
	if(a != b) {
		if(sz[a] > sz[b]) swap(a, b);
		par[a] = b;
		sz[a] += sz[b];
	}
	return;
}
 
void res( void ) {
	for(ll i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
}
 
bool check_un( int a, int b ) {
	return (fn(a) == fn(b));
}
 
pii mst() {
	ll tout = 0;
	ll mout = 0;
	res();
	int tot = 0;
	for(ll i = 0; i < m; i++) {
		if(!check_un(edges[i].a, edges[i].b)) {
			un(edges[i].a, edges[i].b);
			tout += edges[i].t;
			mout += edges[i].m;
			tot++;
		}
		if(tot == n-1) {
			return mp(tout, mout);
		}
	}
	return mp(tout, mout);
}
 
bool s_func_t( Edge a, Edge b ) {
	if(b.t > a.t) return 1;
	if(b.t < a.t) return 0;
	if(b.m > a.m) return 1;
	return 0;
}
 
bool s_func_m( Edge a, Edge b ) {
	if(b.m > a.m) return 1;
	if(b.m < a.m) return 0;
	if(b.t > a.t) return 1;
	return 0;
}
 
bool s_func_xy( Edge a, Edge b ) {
	return ((b.t * x) + (b.m * y) > (a.t * x) + (a.m * y)) ? 1 : 0;
}
 
inline pii daq( pii a, pii b ) {
	y = b.F - a.F;
	x = a.S - b.S;
	sort(edges, edges + m, s_func_xy);
	pii temp1;
	pii temp2;
	pii out = mst();
	if(out.F*x+out.S*y == a.F*x+a.S*y || out.F*x+out.S*y == b.F*x+b.S*y) {
		if(a.F * a.S < b.F * b.S) return a;
		else return b;
	}
	temp1 = daq(a, out);
	temp2 = daq(out, b);
	if(temp1.F * temp1.S < out.F * out.S) out = temp1;
	if(temp2.F * temp2.S < out.F * out.S) out = temp2;
	
	return out;
}
 
int main( void ) {
	
	FIO
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> edges[i].a >> edges[i].b >> edges[i].t >> edges[i].m;
	}
	sort(edges, edges + m, s_func_t);
	pii temp1 = mst();
	sort(edges, edges + m, s_func_m);
	pii temp2 = mst();
	pii sol = daq(temp1, temp2);
	cout << sol.F << " " << sol.S << "\n";
	
	return 0;
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
3 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
4 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
6 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
7 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
8 Incorrect 4 ms 820 KB Unexpected end of file - int32 expected
9 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
10 Incorrect 1 ms 464 KB Unexpected end of file - int32 expected
11 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
12 Incorrect 1 ms 464 KB Unexpected end of file - int32 expected
13 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
14 Incorrect 6 ms 492 KB Unexpected end of file - int32 expected
15 Incorrect 4 ms 348 KB Unexpected end of file - int32 expected
16 Incorrect 88 ms 348 KB Unexpected end of file - int32 expected
17 Incorrect 98 ms 348 KB Unexpected end of file - int32 expected
18 Incorrect 92 ms 540 KB Unexpected end of file - int32 expected
19 Incorrect 760 ms 860 KB Unexpected end of file - int32 expected
20 Incorrect 837 ms 768 KB Unexpected end of file - int32 expected