Submission #43275

#	Time	Username	Problem	Language	Result	Execution time	Memory
43275		ToMoClone	timeismoney (balkan11_timeismoney)	C++14	100 / 100	668 ms	704 KiB

timeismoney

/*input
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
*/
#include <bits/stdc++.h>
using namespace std;

#define Point pair<int, int> 

struct Edge {
	int u, v, val1, val2;
	Edge(int _u, int _v, int _val1, int _val2) :
		u(_u), v(_v), val1(_val1), val2(_val2) {}
};

int Arr[205], n, m, res = 2e9;
Point base;
vector<Edge> edges;
vector<pair<int, int> > trace;

int root(int x) {
	if(x == Arr[x]) return x;
	return Arr[x] = root(Arr[x]);
}

Point Kruskal(int x1, int y1) {
	sort(edges.begin(), edges.end(), [&](const Edge &x, const Edge &y) {
		int X = x.val1 * x1 + x.val2 * y1;
		int Y = y.val1 * x1 + y.val2 * y1;
		return (X != Y) ? (X < Y) : (x.val1 < y.val1);
	});

	for(int i = 1; i <= n; ++i) Arr[i] = i;

	int valx = 0, valy = 0;
	vector<pair<int, int> > Dat;

	for(auto cur : edges) {
		if(root(cur.u) == root(cur.v)) continue;
		if((int)Dat.size() ==  n - 1) break;
		Arr[root(cur.u)] = root(cur.v);

		valx += cur.val1, valy += cur.val2;
		Dat.push_back(make_pair(cur.u, cur.v));
	}

	if(valx * valy < res) {
		res = valx * valy, base = make_pair(valx, valy);
		trace = move(Dat);
	}

	return make_pair(valx, valy);
}

void solve(Point a, Point b) {
	Point X = Kruskal(a.second - b.second, b.first - a.first);
	if(X.first != a.first && X.first != b.first && X.second != a.second &&
		X.second != b.second) solve(a, X), solve(X, b);
}

int main(){
	scanf("%d%d", &n, &m);

	edges.reserve(m);
	for(int i = 0; i < m; ++i) {
		int x, y, t, c; scanf("%d%d%d%d", &x, &y, &t, &c);
		edges.push_back(Edge(x + 1, y + 1, t, c));
	}

	Point maxt = Kruskal(1, 0), maxc = Kruskal(0, 1);
	solve(maxt, maxc);
	
	printf("%d %d\n", base.first, base.second);
	for(auto v : trace) printf("%d %d\n", v.first - 1, v.second - 1);
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:68:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
timeismoney.cpp:72:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, t, c; scanf("%d%d%d%d", &x, &y, &t, &c);
                                                    ^

• Subtask 1: 100 / 100