oj.uz

Submission #15857

# Submission time Handle Problem Language Result Execution time Memory
15857 2015-07-31T13:32:58 Z dohyun0324 timeismoney (balkan11_timeismoney) C++
45 / 100
 16 ms 65536 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,group[210],ord[210];
long long dap=214748364700000000LL;
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[210],arr2[210];
int up(int x)
{
    if(x==group[x]) return x;
    return group[x]=up(group[x]);
}
void upd(point p)
{
    int i;
    if(dap>(long long)p.x*(long long)p.y)
    {
        dap=(long long)p.x*(long long)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

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:71: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:74: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
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1128 KB Output is correct
2 Correct 0 ms 1128 KB Output is correct
3 Correct 0 ms 1128 KB Output is correct
4 Correct 0 ms 1128 KB Output is correct
5 Memory limit exceeded 13 ms 65536 KB Memory limit exceeded
6 Incorrect 0 ms 1128 KB Output isn't correct
7 Memory limit exceeded 16 ms 65536 KB Memory limit exceeded
8 Incorrect 0 ms 1128 KB Output isn't correct
9 Correct 0 ms 1128 KB Output is correct
10 Correct 0 ms 1128 KB Output is correct
11 Correct 0 ms 1128 KB Output is correct
12 Correct 0 ms 1128 KB Output is correct
13 Correct 0 ms 1128 KB Output is correct
14 Incorrect 0 ms 1128 KB Output isn't correct
15 Runtime error 0 ms 1128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 0 ms 1128 KB Output isn't correct
17 Memory limit exceeded 9 ms 65536 KB Memory limit exceeded
18 Incorrect 0 ms 1128 KB Output isn't correct
19 Incorrect 0 ms 1128 KB Output isn't correct
20 Incorrect 0 ms 1128 KB Output isn't correct