#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
const int maxn = 1e5;
int n,m;
struct edge
{
int u,v,t,c;
long long coef;
};
bool cmp(edge x, edge y)
{
return x.coef < y.coef;
}
vector<edge> edges;
long long dot(pair<long long, long long> x, pair<long long, long long> y)
{
return x.first * y.first + x.second * y.second;
}
long long cross(pair<long long, long long> x, pair<long long, long long> y)
{
return x.first * y.second - x.second * y.first;
}
long long area(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c)
{
return cross({b.first - a.first, b.second - a.second}, {c.first - b.first, c.second - b.second});
}
int dsu[maxn+5];
void reset()
{
for(int i = 0; i < n; i++)
dsu[i] = i;
}
int par(int u)
{
if(dsu[u] == u) return u;
return dsu[u] = par(dsu[u]);
}
bool unite(int u, int v)
{
u = par(u);
v = par(v);
if(u == v) return false;
dsu[v] = u;
return true;
}
vector<edge> print;
pair<long long, long long> f(pair<long long, long long> axis, bool yes)
{
for(auto &e: edges)
e.coef = dot(axis,{e.t,e.c});
sort(edges.begin(),edges.end(),cmp);
pair<long long, long long> ans = {0,0};
reset();
for(auto e: edges)
{
if(unite(e.u,e.v))
{
ans.first += e.t;
ans.second += e.c;
if(yes) print.push_back(e);
}
}
return ans;
}
vector<pair<long long, long long>> ans;
vector<pair<long long, long long>> trace;
void divide(pair<long long, long long> lp, pair<long long, long long> rp, pair<long long, long long> l, pair<long long, long long> r)
{
pair<long long, long long> axis = {lp.second - rp.second, rp.first - lp.first};
auto mp = f(axis,0);
// cout << mp.first << ' ' << mp.second << '\n';
if(area(lp,mp,rp) <= 0)
{
ans.push_back(lp);
trace.push_back(l);
ans.push_back(rp);
trace.push_back(r);
return;
}
divide(lp,mp,l,axis);
divide(mp,rp,axis,r);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
edge e;
cin >> e.u >> e.v >> e.t >> e.c;
edges.push_back(e);
}
pair<int,int> x = {1,0};
pair<int,int> y = {0,1};
divide(f(x,0),f(y,0),x,y);
long long total = 1e18;
pair<long long, long long> opt;
pair<long long, long long> optax;
for(int i = 0; i < ans.size(); i++)
{
if(total > ans[i].first * ans[i].second)
{
total = ans[i].first * ans[i].second;
opt = ans[i];
optax = trace[i];
}
}
cout << opt.first << ' ' << opt.second << '\n';
f(optax,1);
for(auto e: print)
{
cout << e.u << ' ' << e.v << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
timeismoney.cpp: In function 'void solve()':
timeismoney.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
5 ms |
788 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
5 ms |
356 KB |
Output is correct |
| 15 |
Correct |
4 ms |
340 KB |
Output is correct |
| 16 |
Correct |
84 ms |
400 KB |
Output is correct |
| 17 |
Correct |
85 ms |
416 KB |
Output is correct |
| 18 |
Correct |
79 ms |
404 KB |
Output is correct |
| 19 |
Correct |
719 ms |
788 KB |
Output is correct |
| 20 |
Correct |
720 ms |
788 KB |
Output is correct |
