Submission #980794

#	Time	Username	Problem	Language	Result	Execution time	Memory
980794		ttttttttttttth	timeismoney (balkan11_timeismoney)	C++17	100 / 100	145 ms	1440 KiB

timeismoney

// Author: Ivan Teo
// Created: Sun May 12 18:10:20 2024

#define TASKNAME "timeismoney"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}
using ld = long double;
using Edge = tuple<ld, int, int, int>;

const int N = 255;
const int M = 1e4 + 5;
int n, m, x[M], y[M], t[M], c[M], b[M];
Edge e[M];

namespace dsu
{
    int p[N];
    void init()
    {
        memset(p, -1, sizeof(p));
    }

    int find(int u)
    {
        return p[u] < 0 ? u : p[u] = find(p[u]);
    }

    bool merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (u == v) return 0;
        if (p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return 1;
    }
}

int T, C;

int get(ld s)
{
    dsu::init();
    fore(i, 1, m) e[i] = {t[i] *s + (255.0 - s) *c[i], x[i] + 1, y[i] + 1, i};
    sort(e + 1, e + 1 + m);
    T = 0, C = 0;
    fore(i, 1, m)
    {
        auto [w, u, v, id] = e[i];
        if (dsu::merge(u, v)) T += t[id], C += c[id], b[id] = 1;
        else b[id] = 0;
    }
    return T * C;
}

void tenarySearch()
{
    long double st = 0, dr = 255.0;
    while((dr - st) > 1e-7)
    {
        long double m1 = (2 * st + dr) / 3;
        long double m2 = (st + 2 * dr) / 3;
        if(get(m1) < get(m2)) dr = m2;
        else st = m1;
    }
    get(st);
    cout << T << ' ' << C << '\n';
    fore(i, 1, m) if (b[i]) cout << x[i] << ' ' << y[i] << '\n';
}


void solve()
{
    cin >> n >> m;
    fore(i, 1, m) cin >> x[i] >> y[i] >> t[i] >> c[i];
    tenarySearch();
    // fore(i, 1, 255) cout << i << ' ' << get(i) << '\n';
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
    {
        freopen(TASKNAME ".inp", "r", stdin),
                freopen(TASKNAME ".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
timeismoney.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(TASKNAME ".inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:108:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                 freopen(TASKNAME ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100