oj.uz

답안 #1009680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009680 2024-06-27T20:12:27 Z Ivo_12 시간이 돈 (balkan11_timeismoney) C++
0 / 100
 2000 ms 64780 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 == 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 344 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
3 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
4 Execution timed out 2099 ms 64780 KB Time limit exceeded
5 Execution timed out 2068 ms 9948 KB Time limit exceeded
6 Execution timed out 2037 ms 9680 KB Time limit exceeded
7 Execution timed out 2035 ms 2120 KB Time limit exceeded
8 Execution timed out 2023 ms 2896 KB Time limit exceeded
9 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
10 Incorrect 0 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 5 ms 480 KB Unexpected end of file - int32 expected
15 Incorrect 4 ms 348 KB Unexpected end of file - int32 expected
16 Execution timed out 2096 ms 1360 KB Time limit exceeded
17 Execution timed out 2064 ms 1364 KB Time limit exceeded
18 Execution timed out 2072 ms 1700 KB Time limit exceeded
19 Execution timed out 2065 ms 2928 KB Time limit exceeded
20 Execution timed out 2032 ms 2648 KB Time limit exceeded