#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm = 100005, maxn = 205;
int n, m;
int x[maxm], y[maxm], t[maxm], c[maxm];
int in[maxm];
int parent[maxn], vel[maxn];
long long ans = 1e18, anst, ansm;
long long t_novi, m_novi;
long long k1, k2;
vector <pair <int, int> > ans2, tr;
int comp (int a, int b){
if (k1 * t[a] + k2 * c[a] < k1 * t[b] + k2 * c[b]){
return 1;
}
return 0;
}
int find (int a){
if (parent[a] == a){
return a;
}
return parent[a] = find(parent[a]);
}
void unite (int p1, int p2){
if (vel[p1] > vel[p2]){
swap(p1, p2);
}
parent[p1] = p2;
vel[p2] += vel[p1];
vel[p1] = 0;
}
void mst (){
tr.clear();
tr.reserve(n - 1);
for (int i = 0; i < m; i++){
in[i] = i;
}
sort(in, in + m, comp);
for (int i = 0; i < n; i++){
vel[i] = 1, parent[i] = i;
}
/*
for (int i = 0; i < m; i++){
cout << x[in[i]] << " " << y[in[i]] << " " << t[in[i]] << endl;
}
cout << endl;*/
t_novi = 0, m_novi = 0;
for (int i = 0; i < m; i++){
int p1 = find(x[in[i]]);
int p2 = find(y[in[i]]);
if (p1 != p2){
unite(p1, p2);
t_novi += t[in[i]];
m_novi += c[in[i]];
tr.push_back({x[in[i]], y[in[i]]});
}
}
if (t_novi * m_novi < ans){
ans = t_novi * m_novi;
anst = t_novi;
ansm = m_novi;
for (int i = 0; i < tr.size(); i++){
ans2[i] = pair<int, int>(tr[i].first, tr[i].second);
}
}
}
void rek (int t1, int m1, int t2, int m2){
//cout << t1 << " " << m1 << " " << t2 << " " << m2 << endl;
double k = (t1 - t2);
//cout << k << endl;
k1 = (m1 - m2), k2 = -k;
mst();
//cout << t_novi << " " << m_novi << endl;
if ((t_novi == t1 and m_novi == m1) or (t_novi == t2 and m_novi == m2)){
return;
}
rek(t1, m1, t_novi, m_novi);
rek(t_novi, m_novi, t2, m2);
}
signed main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++){
cin >> x[i] >> y[i] >> t[i] >> c[i];
}
ans2.resize(n - 1);
k1 = 1, k2 = 0;
mst();
int t1 = t_novi;
int m1 = m_novi;
k1 = 0, k2 = 1;
mst();
int t2 = t_novi;
int m2 = m_novi;
//cout << t1 << " " << m1 << " " << t2 << " " << m2 << endl;
rek(t1, m1, t2, m2);
//cout << ans << "\n";
cout << anst << " " << ansm << "\n";
for (int i = 0; i < ans2.size(); i++){
cout << ans2[i].first << " " << ans2[i].second << "\n";
}
return 0;
}
Compilation message
timeismoney.cpp: In function 'void mst()':
timeismoney.cpp:68:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < tr.size(); i++){
| ~~^~~~~~~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:110:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i = 0; i < ans2.size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2604 KB |
Output is correct |
| 9 |
Execution timed out |
2031 ms |
2396 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2065 ms |
2396 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2058 ms |
2396 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2036 ms |
2392 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2053 ms |
2392 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2072 ms |
2396 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2033 ms |
2396 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2033 ms |
2392 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2044 ms |
2392 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2033 ms |
2392 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2047 ms |
2652 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2054 ms |
2652 KB |
Time limit exceeded |
