oj.uz

Submission #482785

# Submission time Handle Problem Language Result Execution time Memory
482785 2021-10-26T10:27:16 Z solarmagic timeismoney (balkan11_timeismoney) C++17
0 / 100
 75 ms 924 KB 
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using db = long double;
using ll = long long;

db MAX = 1e5;

struct edge{
	ll a, b, t, c;
	db k;
};
 
ll n, m;
vector<edge> v;
vector<ll> p, sz;

ll find(ll x){
	if(x == p[x]) return x;
	return p[x] = find(p[x]);
}
 
void init(ll mid) {
    fill(all(sz), 1);
    iota(all(p), 0);
    for (auto& [a, b, t, c, k] : v) {
        k = c * mid + t * (MAX - mid);
    }
	sort(all(v), [](auto& a, auto& b){return a.k < b.k;});
}

ll solve(db mid){
    init(mid);

    ll solt = 0, solc = 0;
    for (auto [a, b, t, c, k] : v) {
        a = find(a), b = find(b);
        if (a == b) continue;
        solt += t;
        solc += c;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
	}
	return solt * solc;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

	cin >> n >> m;
	v.resize(m);
    p.resize(n);
    sz.resize(n);

    for (auto& [a, b, t, c, val] : v)
        cin >> a >> b >> t >> c;

	db l = 0, r = MAX;
	while(r - l > 1e-7) {
		db m1 = (2*l + r) / 3;
		db m2 = (l + 2*r) / 3;
		if (solve(m1) < solve(m2)) r = m2;
		else l = m1;
	}


    init(l);
    vector<pair<ll,ll>> ans;
	ll sumt = 0, sumc = 0;
    for (auto [a, b, t, c, k] : v) {
        a = find(a), b = find(b);
        if (a == b) continue;
        sumt += t;
        sumc += c;
        ans.emplace_back(a, b);
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
	}
    cout << sumt << ' ' << sumc << "\n";
    for (auto [a, b] : ans) {
        cout << a << ' ' << b << '\n';
    }
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for (auto& [a, b, t, c, val] : v)
      |     ^~~
timeismoney.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |  db l = 0, r = MAX;
      |  ^~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 3 ms 316 KB Output isn't correct
6 Incorrect 3 ms 332 KB Output isn't correct
7 Incorrect 15 ms 440 KB Output isn't correct
8 Incorrect 61 ms 924 KB Output isn't correct
9 Incorrect 0 ms 312 KB Output isn't correct
10 Incorrect 1 ms 204 KB Output isn't correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Incorrect 1 ms 312 KB Output isn't correct
13 Incorrect 1 ms 316 KB Output isn't correct
14 Incorrect 3 ms 332 KB Output isn't correct
15 Incorrect 2 ms 332 KB Output isn't correct
16 Incorrect 14 ms 432 KB Output isn't correct
17 Incorrect 18 ms 440 KB Output isn't correct
18 Incorrect 14 ms 332 KB Output isn't correct
19 Incorrect 75 ms 844 KB Output isn't correct
20 Incorrect 73 ms 844 KB Output isn't correct