Submission #1009968

#TimeUsernameProblemLanguageResultExecution timeMemory
1009968vjudge1timeismoney (balkan11_timeismoney)C++17
100 / 100
754 ms1488 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 205; typedef 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 < n; 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){ Poll novi = solve(a.y - b.y, b.x - a.x); if(eq(a, novi) || eq(b, novi)) 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(1, 0); Poll minY = solve(0, 1); 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 timeMemoryGrader output
Fetching results...