Submission #5075

#	Time	Username	Problem	Language	Result	Execution time	Memory
5075		ainta	timeismoney (balkan11_timeismoney)	C++98	100 / 100	229 ms	1592 KiB

timeismoney

#include<stdio.h>
#define INF 999999999
int w[201][201], n, m, p[201], D[201], num[201][201], C[201], res[201];
long long Res;
bool v[201];
struct Edge{
	int a, b, t, c;
}E[10100];
struct point{
	long long x, y;
}r2;
void UDT(point p){
	if (Res <= p.x*p.y)return;
	Res = p.x*p.y;
	r2 = p;
	int i;
	for (i = 1; i < n; i++)res[i] = C[i];
}
long long ccw(point a, point b, point c){
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
point Do(int dx, int dy){
	int i, T, M, x, t;
	point r;
	r.x = r.y = 0;
	for (i = 0; i < m; i++){
		w[E[i].a][E[i].b] = w[E[i].b][E[i].a] = dy * E[i].t + dx*E[i].c;
	}
	for (i = 0; i < n; i++)D[i] = INF, v[i] = false;
	D[0] = 0, p[0] = 0;
	T = 0;
	while (T != n){
		M = INF;
		for (i = 0; i < n; i++){
			if (!v[i] && D[i] < M)M = D[i], x = i;
		}
		v[x] = true;
		if (x){
			t = num[p[x]][x];
			r.x += E[t].t;
			r.y += E[t].c;
			C[T] = t;
		}
		for (i = 0; i < n; i++){
			if (D[i] > w[x][i])D[i] = w[x][i], p[i] = x;
		}
		T++;
	}
	return r;
}
void Pro(point p1, point p2){
	point p3 = Do(p2.x - p1.x, p1.y - p2.y);
	if (ccw(p1, p2, p3) == 0)return;
	UDT(p3);
	Pro(p1, p3), Pro(p3, p2);
}
int main()
{
	int i, j;
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)for (j = 0; j < n; j++)w[i][j] = INF;
	for (i = 0; i < m; i++){
		scanf("%d%d%d%d", &E[i].a, &E[i].b, &E[i].t, &E[i].c);
		num[E[i].a][E[i].b] = num[E[i].b][E[i].a] = i;
	}
	point p1, p2;
	Res = INF; Res *= Res;
	p1 = Do(0, 1); UDT(p1);
	p2 = Do(1, 0); UDT(p2);
	Pro(p1, p2);
	printf("%lld %lld\n", r2.x, r2.y);
	for (i = 1; i < n; i++)printf("%d %d\n", E[res[i]].a, E[res[i]].b);
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:60: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:63:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &E[i].a, &E[i].b, &E[i].t, &E[i].c);
                                                        ^
timeismoney.cpp: In function 'point Do(int, int)':
timeismoney.cpp:39:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
    t = num[p[x]][x];
               ^

• Subtask 1: 100 / 100