Submission #4932

#	Time	Username	Problem	Language	Result	Execution time	Memory
4932		cki86201	timeismoney (balkan11_timeismoney)	C++98	100 / 100	1006 ms	1316 KiB

timeismoney

#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 (stderr)

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 / 100