oj.uz

답안 #1009618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009618 2024-06-27T17:14:31 Z Ivo_12 시간이 돈 (balkan11_timeismoney) C++
0 / 100
 2000 ms 65536 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];

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) par[b] = a;
	return;
}

void res( void ) {
	for(ll i = 0; i < n; i++) {
		par[i] = i;
	}
}

bool check_un( int a, int b ) {
	return (fn(a) == fn(b));
}

pii mst() {
	ll tout = 0;
	ll mout = 0;
	res();
	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;
		}
	}
	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 == a || out == b) {
		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 1 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 Execution timed out 2061 ms 65536 KB Time limit exceeded
5 Execution timed out 2081 ms 9556 KB Time limit exceeded
6 Execution timed out 2055 ms 10312 KB Time limit exceeded
7 Execution timed out 2069 ms 1872 KB Time limit exceeded
8 Execution timed out 2036 ms 848 KB Time limit exceeded
9 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
10 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
11 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
12 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
13 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
14 Incorrect 6 ms 348 KB Unexpected end of file - int32 expected
15 Incorrect 3 ms 480 KB Unexpected end of file - int32 expected
16 Execution timed out 2099 ms 1268 KB Time limit exceeded
17 Execution timed out 2071 ms 1108 KB Time limit exceeded
18 Execution timed out 2044 ms 1616 KB Time limit exceeded
19 Execution timed out 2055 ms 852 KB Time limit exceeded
20 Execution timed out 2035 ms 848 KB Time limit exceeded