# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1009925 | vjudge1 | timeismoney (balkan11_timeismoney) | C++17 | 610 ms | 1176 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 305;
typedef unsigned long long ll;
struct Edge{
ll a, b, x, y;
};
struct Poll{
ll x = 0, y = 0;
vector<Edge> v = vector<Edge>{};
};
bool eq(Poll& p1, Poll& p2){
return p1.x == p2.x && p1.y == p2.y;
}
ll n, m, boss[MAX];
vector<Edge> edges;
ll findBoss(ll node){
if(boss[node] == node) return node;
return boss[node] = findBoss(boss[node]);
}
Poll solve(ll xCoeff, ll yCoeff){
for(ll i = 0; i < MAX; i++) boss[i] = i;
auto v = edges;
sort(v.begin(), v.end(), [&](const Edge& e1, const Edge& e2){
return (ll)xCoeff*e1.x + (ll)yCoeff*e1.y < (ll)xCoeff*e2.x + (ll)yCoeff*e2.y;
});
Poll ret;
ret.x = 0; ret.y = 0;
for(auto e : v){
ll a = findBoss(e.a), b = findBoss(e.b);
if(a == b) continue;
if(rand() % 2) swap(a, b);
boss[a] = b;
ret.v.push_back(e);
ret.x += e.x;
ret.y += e.y;
}
return ret;
}
void prll(Poll& p){
cout << p.x << ' ' << p.y << '\n';
for(auto e : p.v) cout << e.a << ' ' << e.b << '\n';
}
Poll best;
void rek(Poll& a, Poll& b){
assert(a.x < b.x);
Poll novi = solve(a.y - b.y, b.x - a.x);
if(a.x * (b.y - novi.y) + b.x * (novi.y - a.y) + novi.x * (a.y - b.y) == 0) return;
/*cout << "a\n";
cout << a.x << ' ' << a.y << '\n';
cout << "b\n";
cout << b.x << ' ' << b.y << '\n';
cout << "novi\n";
cout << novi.x << ' ' << novi.y << '\n';*/
if((ll)novi.x * novi.y < (ll)best.x * best.y) best = novi;
rek(a, novi);
rek(novi, b);
}
int main(){
srand(time(0));
cin >> n >> m;
for(ll i = 0; i < m; i++){
Edge e;
cin >> e.a >> e.b >> e.x >> e.y;
edges.push_back(e);
}
Poll minX = solve(100000000, 1);
Poll minY = solve(1, 1000000000);
best = minX;
if((ll)best.x * best.y < (ll)minY.x * minY.y) best = minY;
if(!eq(minX, minY)) rek(minX, minY);
prll(best);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |