oj.uz

Submission #43273

# Submission time Handle Problem Language Result Execution time Memory
43273 2018-03-12T13:33:13 Z ToMoClone timeismoney (balkan11_timeismoney) C++14
0 / 100
 2000 ms 65536 KB 
/*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 * x1 < y.val1 * x1);
	});

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

	int Ans = 0, 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);

		Ans += cur.val1 * x1 + cur.val2 * y1;
		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 != a && X != b) 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, v.second);
}

Compilation message

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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 248 KB Integer 200 violates the range [0, 199]
2 Execution timed out 2041 ms 65536 KB Time limit exceeded
3 Incorrect 1 ms 65536 KB Integer 20 violates the range [0, 19]
4 Execution timed out 2043 ms 65536 KB Time limit exceeded
5 Execution timed out 2055 ms 65536 KB Time limit exceeded
6 Execution timed out 2045 ms 65536 KB Time limit exceeded
7 Execution timed out 2032 ms 65536 KB Time limit exceeded
8 Execution timed out 2037 ms 65536 KB Time limit exceeded
9 Incorrect 1 ms 65536 KB Integer 10 violates the range [0, 9]
10 Incorrect 2 ms 65536 KB Integer 10 violates the range [0, 9]
11 Incorrect 2 ms 65536 KB Integer 20 violates the range [0, 19]
12 Incorrect 2 ms 65536 KB Integer 50 violates the range [0, 49]
13 Incorrect 2 ms 65536 KB Integer 50 violates the range [0, 49]
14 Incorrect 10 ms 65536 KB Integer 100 violates the range [0, 99]
15 Incorrect 6 ms 65536 KB Integer 200 violates the range [0, 199]
16 Execution timed out 2024 ms 65536 KB Time limit exceeded
17 Execution timed out 2036 ms 65536 KB Time limit exceeded
18 Execution timed out 2052 ms 65536 KB Time limit exceeded
19 Execution timed out 2020 ms 65536 KB Time limit exceeded
20 Execution timed out 2036 ms 65536 KB Time limit exceeded