oj.uz

Submission #712457

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

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

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);
			if (i < n){
				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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 340 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 14 ms 372 KB Output is correct
6 Correct 12 ms 340 KB Output is correct
7 Correct 126 ms 468 KB Output is correct
8 Correct 987 ms 1236 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 22 ms 340 KB Output is correct
15 Correct 17 ms 372 KB Output is correct
16 Correct 125 ms 468 KB Output is correct
17 Correct 135 ms 468 KB Output is correct
18 Correct 125 ms 468 KB Output is correct
19 Correct 837 ms 1088 KB Output is correct
20 Correct 868 ms 1380 KB Output is correct