oj.uz

Submission #4932

# Submission time Handle Problem Language Result Execution time Memory
4932 2014-01-19T09:32:06 Z cki86201 timeismoney (balkan11_timeismoney) C++
100 / 100
 1006 ms 1316 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;

int N, M;
int en[2][10010], len[2][10010];
int ord[10010];
int T[2],C[2];
int ans[210][2];
int mx[2] = {1000000,1000000};
int ST, SC;
inline void addedge(int s,int e,int t,int c,int ce){en[0][ce]=s,en[1][ce]=e,len[0][ce]=t,len[1][ce]=c;}

bool comp(const int &x,const int &y){return ST * (len[0][x] - len[0][y]) + SC * (len[1][x] - len[1][y]) < 0;}

struct UnF{
	void init(){for(int i=1;i<=N;i++)p[i] = i, w[i] = 1;}
	int p[210], w[210];
	int Find(int x){
		while(p[x]!=x)x=p[x];
		return x;
	}
	bool Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x==y)return false;
		if(w[x] == w[y])p[x] = y, w[y]++;
		else if(w[x] < w[y])p[x] = y;
		else p[y] = x;
		return true;
	}
}unf;

void init_mst(int m)
{
	if(m == 1)SC = 0, ST = 1;
	else SC = 1, ST = 0;
	sort(ord+1,ord+1+M,comp);
	unf.init();
	int i;
	int tmp[210][2], now = 0;
	for(i=1;i<=M;i++){
		int t = ord[i];
		int x = en[0][t], y = en[1][t];
		if(unf.Union(x,y)){
			T[m] += len[0][t], C[m] += len[1][t];
			now++, tmp[now][0] = x, tmp[now][1] = y;
		}
	}
	if((ll)mx[0]*mx[1] > (ll)C[m] * T[m]){
		for(i=1;i<N;i++)ans[i][0] = tmp[i][0], ans[i][1] = tmp[i][1];
		mx[0] = C[m], mx[1] = T[m];
	}
}

void solve(int t0,int c0,int t1,int c1)
{
	ST = c1-c0, SC = t0-t1;
	ll u = (ll)c1*t0 - (ll)c0*t1;
	sort(ord+1,ord+1+M,comp);
	unf.init();
	int i;
	int tmp[210][2], now = 0;
	int tot[2] = {0,0};
	for(i=1;i<=M;i++){
		int t = ord[i];
		int x = en[0][t], y = en[1][t];
		if(unf.Union(x,y)){
			tot[0] += len[0][t], tot[1] += len[1][t];
			now++, tmp[now][0] = x, tmp[now][1] = y;
		}
	}
	if((ll)mx[0]*mx[1] > (ll)tot[0] * tot[1]){
		for(i=1;i<N;i++)ans[i][0] = tmp[i][0], ans[i][1] = tmp[i][1];
		mx[0] = tot[0], mx[1] = tot[1];
	}
	if((ll)ST * tot[0] + (ll)SC * tot[1] < u){
		solve(t0,c0,tot[0],tot[1]);
		solve(tot[0],tot[1],t1,c1);
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&N,&M);
	int i;
	for(i=1;i<=M;i++){
		int x, y, t, c;
		scanf("%d%d%d%d",&x,&y,&t,&c);
		x++,y++;
		addedge(x, y, t, c, i);
		ord[i] = i;
	}
	init_mst(0);
	init_mst(1);
	solve(T[0],C[0],T[1],C[1]);
	printf("%d %d\n",mx[0],mx[1]);
	for(i=1;i<N;i++)printf("%d %d\n",ans[i][0]-1,ans[i][1]-1);
	return 0;
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:96:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
                     ^
timeismoney.cpp:100:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&x,&y,&t,&c);
                                ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1316 KB Output is correct
2 Correct 0 ms 1316 KB Output is correct
3 Correct 0 ms 1316 KB Output is correct
4 Correct 0 ms 1316 KB Output is correct
5 Correct 0 ms 1316 KB Output is correct
6 Correct 0 ms 1316 KB Output is correct
7 Correct 0 ms 1316 KB Output is correct
8 Correct 6 ms 1316 KB Output is correct
9 Correct 0 ms 1316 KB Output is correct
10 Correct 0 ms 1316 KB Output is correct
11 Correct 0 ms 1316 KB Output is correct
12 Correct 0 ms 1316 KB Output is correct
13 Correct 0 ms 1316 KB Output is correct
14 Correct 3 ms 1316 KB Output is correct
15 Correct 3 ms 1316 KB Output is correct
16 Correct 109 ms 1316 KB Output is correct
17 Correct 119 ms 1316 KB Output is correct
18 Correct 106 ms 1316 KB Output is correct
19 Correct 1006 ms 1316 KB Output is correct
20 Correct 983 ms 1316 KB Output is correct