#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 200;
const int MAXM = 1e4;
const ll INF = 1e18;
struct Edge
{
int u, v, x, y;
};
int N, M;
Edge E[MAXM+10];
pair<ll, pll> ans={INF, {0, 0}};
struct Point { ll x, y; };
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }
bool operator == (const Point &p, const Point &q) { return p.x==q.x && p.y==q.y; }
struct UF
{
int par[MAXN+10];
void init() { for(int i=0; i<=N; i++) par[i]=i; }
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }
} uf;
Point f(ll a, ll b, bool print)
{
int i, j;
Point r={0, 0};
sort(E+1, E+M+1, [&](const Edge &p, const Edge &q) { return p.x*b+p.y*a<q.x*b+q.y*a; });
uf.init();
for(i=1; i<=M; i++)
{
if(uf.Find(E[i].u)!=uf.Find(E[i].v))
{
if(print) printf("%d %d\n", E[i].u-1, E[i].v-1);
uf.Union(E[i].u, E[i].v);
r.x+=E[i].x;
r.y+=E[i].y;
}
}
return r;
}
void dnc(Point p, Point q)
{
int i, j;
if(p==q) return;
ll a=q.x-p.x, b=p.y-q.y;
Point r=f(a, b, 0);
ans=min(ans, {r.x*r.y, {a, b}});
Point v1=p-r, v2=q-r;
if(v1.x*v2.y-v1.y*v2.x<=0) return;
dnc(p, r);
dnc(r, q);
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i=1; i<=M; i++) scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].x, &E[i].y), E[i].u++, E[i].v++;
Point p=f(0, 1, 0), q=f(1, 0, 0);
ans=min(ans, {p.x*p.y, {0, 1}});
ans=min(ans, {q.x*q.y, {1, 0}});
dnc(p, q);
Point r=f(ans.second.first, ans.second.second, 0);
printf("%lld %lld\n", r.x, r.y);
f(ans.second.first, ans.second.second, 1);
}
Compilation message
timeismoney.cpp: In function 'Point f(ll, ll, bool)':
timeismoney.cpp:35:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
timeismoney.cpp: In function 'void dnc(Point, Point)':
timeismoney.cpp:56:6: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
timeismoney.cpp:56:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:70:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
timeismoney.cpp:72:7: 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:85: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=M; i++) scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].x, &E[i].y), E[i].u++, E[i].v++;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
6 ms |
376 KB |
Output is correct |
| 8 |
Correct |
10 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
| 11 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 12 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 13 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 14 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 15 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 16 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 17 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 18 |
Incorrect |
6 ms |
380 KB |
Output isn't correct |
| 19 |
Incorrect |
11 ms |
504 KB |
Output isn't correct |
| 20 |
Incorrect |
12 ms |
504 KB |
Output isn't correct |
