Submission #457982

# Submission time Handle Problem Language Result Execution time Memory
457982 2021-08-07T16:48:59 Z Plurm timeismoney (balkan11_timeismoney) C++11
0 / 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));
	}else{
		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:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d%d%d",&x,&y,&t,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 23160 KB Time limit exceeded
2 Runtime error 648 ms 65540 KB Execution killed with signal 9
3 Runtime error 811 ms 65540 KB Execution killed with signal 9
4 Execution timed out 2078 ms 62384 KB Time limit exceeded
5 Execution timed out 2077 ms 11384 KB Time limit exceeded
6 Execution timed out 2056 ms 14652 KB Time limit exceeded
7 Execution timed out 2085 ms 2592 KB Time limit exceeded
8 Execution timed out 2068 ms 800 KB Time limit exceeded
9 Runtime error 616 ms 65540 KB Execution killed with signal 9
10 Runtime error 1280 ms 65540 KB Execution killed with signal 9
11 Runtime error 799 ms 65540 KB Execution killed with signal 9
12 Execution timed out 2086 ms 62544 KB Time limit exceeded
13 Execution timed out 2093 ms 62756 KB Time limit exceeded
14 Execution timed out 2083 ms 11676 KB Time limit exceeded
15 Execution timed out 2086 ms 13668 KB Time limit exceeded
16 Execution timed out 2085 ms 2244 KB Time limit exceeded
17 Execution timed out 2084 ms 2420 KB Time limit exceeded
18 Execution timed out 2099 ms 2244 KB Time limit exceeded
19 Execution timed out 2055 ms 848 KB Time limit exceeded
20 Execution timed out 2082 ms 780 KB Time limit exceeded