oj.uz

Submission #43274

# Submission time Handle Problem Language Result Execution time Memory
43274 2018-03-12T13:34:26 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.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, v.second);
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:69: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:73: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 2 ms 248 KB Integer 200 violates the range [0, 199]
2 Runtime error 1896 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 2 ms 65536 KB Integer 20 violates the range [0, 19]
4 Execution timed out 2054 ms 65536 KB Time limit exceeded
5 Execution timed out 2057 ms 65536 KB Time limit exceeded
6 Execution timed out 2032 ms 65536 KB Time limit exceeded
7 Execution timed out 2054 ms 65536 KB Time limit exceeded
8 Execution timed out 2057 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 1 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 6 ms 65536 KB Integer 100 violates the range [0, 99]
15 Incorrect 5 ms 65536 KB Integer 200 violates the range [0, 199]
16 Incorrect 76 ms 65536 KB Integer 200 violates the range [0, 199]
17 Incorrect 78 ms 65536 KB Integer 200 violates the range [0, 199]
18 Incorrect 74 ms 65536 KB Integer 200 violates the range [0, 199]
19 Incorrect 610 ms 65536 KB Integer 200 violates the range [0, 199]
20 Incorrect 653 ms 65536 KB Integer 200 violates the range [0, 199]