#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[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>(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);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
18060 KB |
Execution timed out |
| 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 |
Execution timed out |
2000 ms |
1460 KB |
Execution timed out |
| 7 |
Memory limit exceeded |
6 ms |
65536 KB |
Memory limit exceeded |
| 8 |
Execution timed out |
2000 ms |
16976 KB |
Execution timed out |
| 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 |
19 ms |
65536 KB |
Memory limit exceeded |
| 18 |
Execution timed out |
2000 ms |
25768 KB |
Execution timed out |
| 19 |
Incorrect |
0 ms |
1128 KB |
Output isn't correct |
| 20 |
Incorrect |
0 ms |
1128 KB |
Output isn't correct |
