oj.uz

Submission #480777

# Submission time Handle Problem Language Result Execution time Memory
480777 2021-10-18T03:33:46 Z daongocha timeismoney (balkan11_timeismoney) C++14
50 / 100
 1020 ms 976 KB 
#include <bits/stdc++.h>

#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
 
using namespace std;

const int MAXN = 205;

struct edge {
	int u, v, t, c;
};

#define ld long double
const ld EPS = 1e-9;
ld q;

ld num(edge a) {
	return q * a.t + (1e6 - q) * a.c;
}

bool cmp(edge a, edge b) {
	return num(a) + EPS < num(b);
}

vector<edge> edges;
int n, m;

int dsu[MAXN];

int Find(int u) {
	if (u == dsu[u]) return u;
	return dsu[u] = Find(dsu[u]);
}

void Union(int u, int v) {
	u = Find(u), v = Find(v);
	if (u != v) dsu[v] = u;
}

int solve(ld okayge) {
	q = okayge;
	sort(edges.begin(), edges.end(), cmp);
	for (int i = 1; i <= n; i++) dsu[i] = i;
	int tott = 0, totc = 0;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			tott += e.t;
			totc += e.c;
		}
	}
	return tott * totc;
}

void print(ld okayge) {
	q = okayge;
	sort(edges.begin(), edges.end(), cmp);
	for (int i = 1; i <= n; i++) dsu[i] = i;
	int tott = 0, totc = 0;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			tott += e.t;
			totc += e.c;
		}
	}
	cout << tott << ' ' << totc << '\n';
	for (int i = 1; i <= n; i++) dsu[i] = i;
	for (auto e: edges) {
		int u = e.u, v = e.v;
		if (Find(u) != Find(v)) {
			Union(u, v);
			cout << u - 1 << ' ' << v - 1 << '\n';
		}
	}
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m;

	q = 0.1;

	for (int i = 1, u, v, t, c; i <= m; i++) {
		cin >> u >> v >> t >> c;
		u++; v++;
		edges.push_back({u, v, t, c});
	}

	ld l = 0, r = 1e6;
	for (int i = 1; i <= 400; i++) {
		ld lm = l + (r - l) / 3, rm = r - (r - l) / 3;
		if (solve(lm) > solve(rm)) l = lm;
		else r = rm;
	}

	print(l);
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 332 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 6 ms 320 KB Output is correct
5 Correct 25 ms 460 KB Output is correct
6 Correct 21 ms 332 KB Output is correct
7 Correct 138 ms 420 KB Output is correct
8 Correct 874 ms 848 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Correct 2 ms 204 KB Output is correct
11 Incorrect 2 ms 204 KB Output isn't correct
12 Incorrect 6 ms 204 KB Output isn't correct
13 Incorrect 5 ms 204 KB Output isn't correct
14 Incorrect 29 ms 332 KB Output isn't correct
15 Incorrect 25 ms 332 KB Output isn't correct
16 Incorrect 174 ms 332 KB Output isn't correct
17 Incorrect 178 ms 460 KB Output isn't correct
18 Incorrect 157 ms 424 KB Output isn't correct
19 Incorrect 1020 ms 976 KB Output isn't correct
20 Correct 959 ms 920 KB Output is correct