oj.uz

답안 #1009675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009675 2024-06-27T19:52:31 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
50 / 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 = 2e2+10, M = 1e4+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));
}

pair < vector < Edge >, pii > mst() {
	ll tout = 0;
	ll mout = 0;
	vector < Edge > edgout;
	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;
			edgout.pb(edges[i]);
		}
	}
	return mp(edgout, 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;
}

pair < vector < Edge >, pii > daq( pair < vector < Edge >, pii >& a, pair < vector < Edge >, pii >& b ) {
	y = b.S.F - a.S.F;
	x = a.S.S - b.S.S;
	sort(edges, edges + m, s_func_xy);
	pair < vector < Edge >, pii > out = mst();
	if(out.S == a.S || out.S == b.S) {
		if(a.S.F * a.S.S < b.S.F * b.S.S) return a;
		else return b;
	}
	pair < vector < Edge >, pii > temp1 = daq(a, out);
	pair < vector < Edge >, pii > temp2 = daq(out, b);
	if(temp1.S.F * temp1.S.S < out.S.F * out.S.S) out = temp1;
	if(temp2.S.F * temp2.S.S < out.S.F * out.S.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);
	pair < vector < Edge >, pii > temp1 = mst();
	sort(edges, edges + m, s_func_m);
	pair < vector < Edge >, pii > temp2 = mst();
	pair < vector < Edge >, pii > sol = daq(temp1, temp2);
	cout << sol.S.F << " " << sol.S.S << "\n";
	for(int i = 0; i < (int) sol.F.size(); i++) {
		cout << sol.F[i].a << " " << sol.F[i].b << "\n";
	}
	
	return 0;
}

Subtask #1
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 113 ms 65536 KB Execution killed with signal 9
5 Runtime error 306 ms 65536 KB Execution killed with signal 9
6 Runtime error 159 ms 65536 KB Execution killed with signal 9
7 Runtime error 922 ms 65536 KB Execution killed with signal 9
8 Execution timed out 2070 ms 25688 KB Time limit exceeded
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 4 ms 588 KB Output is correct
16 Runtime error 1761 ms 65536 KB Execution killed with signal 9
17 Runtime error 1797 ms 65536 KB Execution killed with signal 9
18 Runtime error 1139 ms 65536 KB Execution killed with signal 9
19 Execution timed out 2043 ms 14204 KB Time limit exceeded
20 Execution timed out 2080 ms 19308 KB Time limit exceeded