// 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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
28 ms |
668 KB |
Output is correct |
| 8 |
Correct |
145 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
4 ms |
500 KB |
Output is correct |
| 15 |
Correct |
2 ms |
348 KB |
Output is correct |
| 16 |
Correct |
21 ms |
604 KB |
Output is correct |
| 17 |
Correct |
23 ms |
604 KB |
Output is correct |
| 18 |
Correct |
24 ms |
552 KB |
Output is correct |
| 19 |
Correct |
123 ms |
1440 KB |
Output is correct |
| 20 |
Correct |
125 ms |
1440 KB |
Output is correct |
