oj.uz

답안 #712440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
712440 2023-03-18T19:28:24 Z study 시간이 돈 (balkan11_timeismoney) C++17
5 / 100
 82 ms 596 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 201, nbIter = 10000,inf = sqrt(LLONG_MAX/2);

int comp[N],siz[N],t[N],c[N],x[N],y[N];
int fin1=inf,fin2=inf;
vector<pair<int,int>> res;

int getComp(int node){
	if (comp[node] != node) comp[node] = getComp(comp[node]);
	return comp[node];
}

bool merge(int a, int b){
	a = getComp(a);
	b = getComp(b);
	if (a != b){
		if (siz[a] < siz[b]) swap(a,b);
		siz[a] += siz[b];
		comp[b] = a;
		return true;
	}
	return false;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for (int i=0; i<m; ++i){
		cin >> x[i] >> y[i] >> t[i] >> c[i];
	}
	for (int nb=0; nb<=nbIter; ++nb){
		vector<pair<int,int>> v,ans;
		for (int i=0; i<n; ++i){
			v.emplace_back(t[i]*(nbIter-nb)+c[i]*nb,i);
			comp[i] = i;
			siz[i] = 1;
		}
		sort(v.begin(),v.end());
		int sum1 = 0, sum2 = 0;
		for (auto [comp,id]:v){
			if (merge(x[id],y[id])){
				sum1 += t[id];
				sum2 += c[id];
				ans.emplace_back(x[id],y[id]);
			}
		}
		if (sum1*sum2 < fin1*fin2){
			res = ans;
			fin1 = sum1;
			fin2 = sum2;
		} 
	}
	cout << fin1 << ' ' << fin2 << '\n';
	for (auto i:res) cout << i.first << ' ' << i.second << '\n';
	return 0;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 340 KB Output is correct
2 Incorrect 4 ms 328 KB Output isn't correct
3 Incorrect 7 ms 332 KB Output isn't correct
4 Incorrect 15 ms 340 KB Output isn't correct
5 Incorrect 35 ms 212 KB Output isn't correct
6 Incorrect 80 ms 340 KB Output isn't correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 588 KB Execution killed with signal 11
9 Incorrect 4 ms 212 KB Output isn't correct
10 Incorrect 6 ms 328 KB Output isn't correct
11 Incorrect 8 ms 328 KB Output isn't correct
12 Incorrect 16 ms 332 KB Output isn't correct
13 Incorrect 16 ms 212 KB Output isn't correct
14 Incorrect 38 ms 340 KB Output isn't correct
15 Incorrect 82 ms 340 KB Output isn't correct
16 Runtime error 1 ms 468 KB Execution killed with signal 11
17 Runtime error 1 ms 472 KB Execution killed with signal 11
18 Runtime error 1 ms 464 KB Execution killed with signal 11
19 Runtime error 1 ms 596 KB Execution killed with signal 11
20 Runtime error 1 ms 596 KB Execution killed with signal 11