Submission #15855

#	Time	Username	Problem	Language	Result	Execution time	Memory
15855		dohyun0324	timeismoney (balkan11_timeismoney)	C++98	40 / 100	2000 ms	65536 KiB

timeismoney

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,group[210],ord[210],dap=2147483647;
struct data{
    int x,y,t,c,p;
    bool operator<(const data&r)const{
        return p<r.p;
    }
}e[210];
struct point{
    int x,y;
}ans;
point p1,p2,arr[110],arr2[110];
int up(int x)
{
    if(x==group[x]) return x;
    return group[x]=up(group[x]);
}
void upd(point p)
{
    int i;
    if(dap>p.x*p.y)
    {
        dap=p.x*p.y;
        ans=p;
        for(i=1;i<=n-1;i++) arr2[i]=arr[i];
    }
}
int union_find(int x,int y)
{
    int p=up(x),q=up(y);
    if(p==q) return 0;
    if(ord[p]>ord[q]) group[q]=p;
    else if(ord[p]<ord[q]) group[p]=q;
    else group[p]=q, ord[q]++;
    return 1;
}
point pro(int t,int c)
{
    int i,s,w=0;
    point pp; pp.x=pp.y=0;
    for(i=1;i<=m;i++) e[i].p=e[i].t*t+e[i].c*c;
    for(i=1;i<=n;i++) ord[i]=0, group[i]=i;
    sort(e+1,e+m+1);
    for(i=1;i<=m;i++)
    {
        s=union_find(e[i].x,e[i].y);
        if(s==0) continue;
        pp.x+=e[i].t, pp.y+=e[i].c;
        w++; arr[w].x=e[i].x-1; arr[w].y=e[i].y-1;
        if(w==n-1) break;
    }
    return pp;
}
int ccw(point p,point q,point r)
{
    return (r.y-p.y)*(r.x-q.x)-(r.y-q.y)*(r.x-p.x);
}
void dfs(point p,point q)
{
    point r=pro(-p.y+q.y,p.x-q.x);
    if(ccw(p,q,r)==0) return;
    upd(r);
    dfs(p,r); dfs(r,q);
}
int main()
{
    int i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].t,&e[i].c);
        e[i].x++; e[i].y++;
    }
    p1=pro(0,1); upd(p1);// 가장 아래
    p2=pro(1,0); upd(p2); // 가장 왼쪽
    dfs(p1,p2);
    printf("%d %d\n",ans.x,ans.y);
    for(i=1;i<=n-1;i++) printf("%d %d\n",arr2[i].x,arr2[i].y);
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:70:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
timeismoney.cpp:73:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].t,&e[i].c);
                                                             ^

• Subtask 1: 40 / 100