Submission #457981

# Submission time Handle Problem Language Result Execution time Memory
457981 2021-08-07T16:47:13 Z Plurm timeismoney (balkan11_timeismoney) C++11
40 / 100
2000 ms 65540 KB
#include <bits/stdc++.h>
using namespace std;

function<bool(tuple<int,int,int,int>,tuple<int,int,int,int>)> get_comp(int a, int b){
	return [a, b](tuple<int,int,int,int> x, tuple<int,int,int,int> y){
		return a*get<2>(x) + b*get<3>(x) < a*get<2>(y) + b*get<3>(y);
	};
}

int n, m;
vector<tuple<int,int,int,int> > edges;

class DSU{
	private:
		int p[256];
	public:
		DSU(){
			memset(p, -1, sizeof(p));
		}
		int f(int u){
			if(p[u] == -1) return u;
			else return p[u] = f(p[u]);
		}
		bool u(int x, int y){
			x = f(x); y = f(y);
			if(x == y) return false;
			p[x] = y;
			return true;
		}
};

map<pair<int,int>, tuple<long long,int,int> > memoiz;

tuple<long long,int,int> compute_value(int a, int b){
	if(memoiz.count(make_pair(a, b))) return memoiz[make_pair(a,b)];
	// Careful! This function takes O(M log M + N)
	sort(edges.begin(), edges.end(), get_comp(a,b));
	DSU d;
	int st = 0, sc = 0;
	for(auto e : edges){
		int x, y, t, c; tie(x, y, t, c) = e;
		if(d.u(x, y)){
			st += t;
			sc += c;
		}
	}
	return memoiz[make_pair(a,b)] = make_tuple(1ll * st * sc, a, b);
}

tuple<long long,int,int> track_min(tuple<long long,int,int> x, tuple<long long,int,int> y){
	if(get<0>(x) > get<0>(y)) return y;
	else return x;
}

tuple<long long,int,int> search(int a1, int b1, int a2, int b2){
	auto lv = compute_value(a1, b1);
	auto rv = compute_value(a2, b2);
	int am = a1 + a2;
	int bm = b1 + b2;
	auto ret = track_min(lv, rv);
	if(get<0>(lv) != get<0>(rv)){
		ret = track_min(ret, search(a1, b1, am, bm));
		ret = track_min(ret, search(am, bm, a2, b2));
	}
	return ret;
}

int main(){
	scanf("%d%d",&n,&m);
	int x, y, t, c;
	for(int i = 0; i < m; i++){
		scanf("%d%d%d%d",&x,&y,&t,&c);
		edges.emplace_back(x,y,t,c);
	}
	auto ans = search(1, 0, 0, 1);
	sort(edges.begin(), edges.end(), get_comp(get<1>(ans), get<2>(ans)));
	DSU d;
	int st = 0, sc = 0;
	vector<pair<int,int> > ansvec;
	for(auto e : edges){
		tie(x, y, t, c) = e;
		if(d.u(x, y)){
			st += t;
			sc += c;
			ansvec.emplace_back(x, y);
		}
	}
	printf("%d %d\n", st, sc);
	for(auto p : ansvec){
		printf("%d %d\n", p.first, p.second);
	}
	return 0;
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d%d%d",&x,&y,&t,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 7 ms 588 KB Output is correct
9 Runtime error 862 ms 65540 KB Execution killed with signal 9
10 Runtime error 1076 ms 65540 KB Execution killed with signal 9
11 Runtime error 1028 ms 65540 KB Execution killed with signal 9
12 Runtime error 1872 ms 65540 KB Execution killed with signal 9
13 Runtime error 1924 ms 65540 KB Execution killed with signal 9
14 Execution timed out 2076 ms 13020 KB Time limit exceeded
15 Execution timed out 2081 ms 16172 KB Time limit exceeded
16 Execution timed out 2065 ms 2688 KB Time limit exceeded
17 Execution timed out 2073 ms 2648 KB Time limit exceeded
18 Execution timed out 2073 ms 2756 KB Time limit exceeded
19 Execution timed out 2062 ms 752 KB Time limit exceeded
20 Execution timed out 2074 ms 1012 KB Time limit exceeded