Submission #228267

#	Time	Username	Problem	Language	Result	Execution time	Memory
228267		urd05	timeismoney (balkan11_timeismoney)	C++14	70 / 100	2090 ms	1660 KiB

timeismoney

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

#define int long long

int n,m;

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

Edge edge[10000];
int one,two;
int cnt=0;

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

int opt1=-1;
int opt2=-1;
long long ret1=1e6;
long long ret2=1e6;

int p[200];

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

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

void solve(int x1,int y1,int x2,int y2) {
    if (x1==x2&&y1==y2) {
        return;
    }
    one=y1-y2;
    two=x2-x1;
    int x=0;
    int y=0;
    sort(edge,edge+m,comp);
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        cnt++;
        if (find(edge[i].s)!=find(edge[i].e)) {
            x+=edge[i].t;
            y+=edge[i].c;
            merge(edge[i].s,edge[i].e);
        }
    }
    if ((long long)x*(long long)y<ret1*ret2) {
        ret1=x;
        ret2=y;
        opt1=y1-y2;
        opt2=x2-x1;
    }
    if ((x!=x2)||(y!=y2))
        solve(x1,y1,x,y);
    if (x!=x1||y!=y1)
        solve(x,y,x2,y2);
}

main(void) {
    //mt19937 rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
    //uniform_int_distribution<int> ran(0, 2147483647);
    scanf("%d %d\n",&n,&m);
    n=100;
    m=2000;
    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);
        //edge[i].s=ran(rd)%n;
        //edge[i].e=ran(rd)%n;
        //edge[i].t=ran(rd)%256;
        //edge[i].c=ran(rd)%256;
    }
    one=400*n+100000;
    two=1;
    int x1=0;
    int x2=0;
    int y1=0;
    int y2=0;
    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)) {
            x1+=edge[i].t;
            y1+=edge[i].c;
            merge(edge[i].s,edge[i].e);
        }
    }
    if (x1*(long long)y1<ret1*ret2) {
        ret1=x1;
        ret2=y1;
        opt1=1;
        opt2=0;
    }
    one=1;
    two=400*n+100000;
    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)) {
            x2+=edge[i].t;
            y2+=edge[i].c;
            merge(edge[i].s,edge[i].e);
        }
    }
    if (x2*(long long)y2<ret1*ret2) {
        ret1=x2;
        ret2=y2;
        opt1=0;
        opt2=1;
    }
    solve(x1,y1,x2,y2);
    //printf("%d\n",cnt);
    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:76:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void) {
          ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:79:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d %d\n",&n,&m);
                     ~~   ^
timeismoney.cpp:79:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
timeismoney.cpp:83:74: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d %d %d %d\n",&edge[i].s,&edge[i].e,&edge[i].t,&edge[i].c);
                               ~~~~~~~~~~                                 ^
timeismoney.cpp:83:74: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
timeismoney.cpp:83:74: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
timeismoney.cpp:83:74: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
timeismoney.cpp:129: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:129:31: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
timeismoney.cpp:137:49: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
             printf("%d %d\n",edge[i].s,edge[i].e);
                              ~~~~~~~~~          ^
timeismoney.cpp:137:49: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
timeismoney.cpp:79: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:83: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: 70 / 100