Submission #228191

#	Time	Username	Problem	Language	Result	Execution time	Memory
228191		urd05	timeismoney (balkan11_timeismoney)	C++14	0 / 100	2098 ms	640 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

int n,m;

struct Edge {
    int s,e,t,c;
};

Edge edge[10000];
int one,two;

bool comp(Edge a,Edge b) {
    return one*a.t+two*a.c<one*b.t+two*b.c;
}

int p[200];

int find(int a) {
    if (p[a]<0) {
        return a;
    }
    p[a]=find(p[a]);
    return p[a];
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

int main(void) {
    scanf("%d %d\n",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%d %d %d %d\n",&edge[i].s,&edge[i].e,&edge[i].t,&edge[i].c);
    }
    int opt1=-1;
    int opt2=-1;
    long long ret1=1e6;
    long long ret2=1e6;
    for(int i=0;i<256*n;i++) {
        for(int j=0;j<256*n;j++) {
            one=i;
            two=j;
            sort(edge,edge+m,comp);
            memset(p,-1,sizeof(p));
            long long tsum=0;
            long long csum=0;
            for(int k=0;k<m;k++) {
                if (find(edge[k].s)!=find(edge[k].e)) {
                    merge(edge[k].s,edge[k].e);
                    tsum+=edge[k].t;
                    csum+=edge[k].c;
                }
            }
            if (tsum*csum<ret1*ret2) {
                opt1=i;
                opt2=j;
                ret1=tsum;
                ret2=csum;
            }
        }
    }
    printf("%d %d\n",ret1,ret2);
    one=opt1;
    two=opt2;
    sort(edge,edge+m,comp);
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        if (find(edge[i].s)!=find(edge[i].e)) {
            merge(edge[i].s,edge[i].e);
            printf("%d %d\n",edge[i].s,edge[i].e);
        }
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:68:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%d %d\n",ret1,ret2);
                               ^
timeismoney.cpp:68:31: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
timeismoney.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d\n",&edge[i].s,&edge[i].e,&edge[i].t,&edge[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100