oj.uz

Submission #712454

# Submission time Handle Problem Language Result Execution time Memory
712454 2023-03-18T19:37:10 Z study timeismoney (balkan11_timeismoney) C++17
80 / 100
 2000 ms 1268 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 201, M = 10000, nbIter = 10000,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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 340 KB Output isn't correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 28 ms 340 KB Output is correct
5 Correct 175 ms 352 KB Output is correct
6 Correct 132 ms 356 KB Output is correct
7 Correct 1345 ms 468 KB Output is correct
8 Execution timed out 2072 ms 1208 KB Time limit exceeded
9 Correct 6 ms 340 KB Output is correct
10 Correct 12 ms 352 KB Output is correct
11 Correct 9 ms 344 KB Output is correct
12 Correct 26 ms 360 KB Output is correct
13 Correct 27 ms 340 KB Output is correct
14 Correct 197 ms 356 KB Output is correct
15 Correct 138 ms 340 KB Output is correct
16 Correct 1248 ms 468 KB Output is correct
17 Correct 1292 ms 468 KB Output is correct
18 Correct 1301 ms 468 KB Output is correct
19 Execution timed out 2063 ms 1268 KB Time limit exceeded
20 Execution timed out 2052 ms 1240 KB Time limit exceeded