| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 726886 | josanneo22 | timeismoney (balkan11_timeismoney) | C++17 | 45 ms | 860 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize(Ofast)
#pragma GCC optimization (unroll-loops)
#pragma GCC target(avx,avx2,fma)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
struct edge {
int u, v;
int v1, v2;
ld val;
bool operator<(const edge& b)const {
return val < b.val;
}
};
const ld R = 1e5;
int n, m;
int par[210];
vector<edge> e;
int pn(int u) { return u == par[u] ? u : (par[u] = pn(par[u])); }
void us(int a, int b) {
a = pn(a), b = pn(b);
par[b] = a;
}
pair<ll, vector<edge>> f(ld x) {
for (int i = 0; i <= n; i++)par[i] = i;
for (auto& it : e)it.val = it.v1 * x + it.v2 * (R - x);
sort(e.begin(), e.end());
ll s1 = 0, s2 = 0;
vector<edge> r;
for (auto& it : e) {
if (pn(it.u) != pn(it.v)) {
us(it.u, it.v);
s1 += it.v1;
s2 += it.v2;
r.pb(it);
}
}
return { s1 * s2,r };
}
int main() {
ios::sync_with_stdio(stdin); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, v1, v2;
cin >> x >> y >> v1 >> v2;
e.pb({ x,y,v1,v2 });
}
ld lo = 0, hi = R;
while (abs(lo - hi) > 2) {
ld m1 = (lo * 2 + hi) / 3;
ld m2 = (lo + hi * 2) / 3;
if (f(m1).fi < f(m2).fi) hi = m2;
else lo = m1;
}
vector<edge> r = f(lo).se;
ll s1 = 0, s2 = 0;
for (auto& it : r) {
s1 += it.v1;
s2 += it.v2;
}
cout << s1 << ' ' << s2 << '\n';
for (auto& it : r)cout << it.u << ' ' << it.v << '\n';
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||