oj.uz

Submission #726886

# Submission time Handle Problem Language Result Execution time Memory
726886 2023-04-19T13:43:22 Z josanneo22 timeismoney (balkan11_timeismoney) C++17
100 / 100
 45 ms 860 KB 
#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

timeismoney.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization (unroll-loops)
      | 
timeismoney.cpp:2:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
    2 | #pragma GCC optimize(Ofast)
      |                      ^~~~~
timeismoney.cpp:4:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
    4 | #pragma GCC target(avx,avx2,fma)
      |                    ^~~
timeismoney.cpp:5:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
    5 | #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
      |                    ^~~
timeismoney.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
timeismoney.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
timeismoney.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
timeismoney.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
timeismoney.cpp:63:31: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   63 |  bool operator<(const edge& b)const {
      |                               ^~~~~
timeismoney.cpp:63:31: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:63:31: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:63:31: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:72:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | int pn(int u) { return u == par[u] ? u : (par[u] = pn(par[u])); }
      |             ^
timeismoney.cpp:72:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:72:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:72:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:74:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   74 | void us(int a, int b) {
      |                     ^
timeismoney.cpp:74:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:74:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:74:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:78:30: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   78 | pair<ll, vector<edge>> f(ld x) {
      |                              ^
timeismoney.cpp:78:30: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:78:30: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:78:30: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:94:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   94 | int main() {
      |          ^
timeismoney.cpp:94:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:94:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
timeismoney.cpp:94:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 30 ms 848 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 2 ms 212 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 8 ms 424 KB Output is correct
18 Correct 8 ms 424 KB Output is correct
19 Correct 45 ms 860 KB Output is correct
20 Correct 43 ms 844 KB Output is correct