oj.uz

Submission #712463

# Submission time Handle Problem Language Result Execution time Memory
712463 2023-03-18T19:48:31 Z study timeismoney (balkan11_timeismoney) C++17
100 / 100
 992 ms 1692 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 201, M = 10000, nbIter = 1000,inf = 1e9;

int comp[N],siz[N],t[M],c[M],x[M],y[M];
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<m; ++i){
			v.emplace_back(t[i]*(nbIter-nb)+c[i]*nb,i);
		}
		for (int i=0; i<n; ++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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 16 ms 388 KB Output is correct
6 Correct 12 ms 388 KB Output is correct
7 Correct 128 ms 476 KB Output is correct
8 Correct 992 ms 1352 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 22 ms 384 KB Output is correct
15 Correct 18 ms 340 KB Output is correct
16 Correct 131 ms 468 KB Output is correct
17 Correct 154 ms 480 KB Output is correct
18 Correct 127 ms 592 KB Output is correct
19 Correct 851 ms 1692 KB Output is correct
20 Correct 856 ms 1500 KB Output is correct