oj.uz

Submission #5075

# Submission time Handle Problem Language Result Execution time Memory
5075 2014-02-01T23:47:52 Z ainta timeismoney (balkan11_timeismoney) C++
100 / 100
 229 ms 1592 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1592 KB Output is correct
2 Correct 0 ms 1592 KB Output is correct
3 Correct 0 ms 1592 KB Output is correct
4 Correct 0 ms 1592 KB Output is correct
5 Correct 0 ms 1592 KB Output is correct
6 Correct 0 ms 1592 KB Output is correct
7 Correct 0 ms 1592 KB Output is correct
8 Correct 3 ms 1592 KB Output is correct
9 Correct 0 ms 1592 KB Output is correct
10 Correct 0 ms 1592 KB Output is correct
11 Correct 0 ms 1592 KB Output is correct
12 Correct 0 ms 1592 KB Output is correct
13 Correct 0 ms 1592 KB Output is correct
14 Correct 6 ms 1592 KB Output is correct
15 Correct 23 ms 1592 KB Output is correct
16 Correct 109 ms 1592 KB Output is correct
17 Correct 116 ms 1592 KB Output is correct
18 Correct 123 ms 1592 KB Output is correct
19 Correct 223 ms 1592 KB Output is correct
20 Correct 229 ms 1592 KB Output is correct