Submission #1009351

#TimeUsernameProblemLanguageResultExecution timeMemory
1009351vjudge1timeismoney (balkan11_timeismoney)C++17
90 / 100
717 ms908 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 205; struct Edge{ int a, b, x, y; }; struct Point{ int x = 0, y = 0; vector<Edge> v = vector<Edge>{}; }; bool eq(Point& p1, Point& p2){ return p1.x == p2.x && p1.y == p2.y; } int n, m, boss[MAX]; vector<Edge> edges; int findBoss(int node){ if(boss[node] == node) return node; return boss[node] = findBoss(boss[node]); } Point solve(int xCoeff, int yCoeff){ for(int i = 0; i < n; i++) boss[i] = i; auto v = edges; sort(v.begin(), v.end(), [&](const Edge& e1, const Edge& e2){ return xCoeff*e1.x + yCoeff*e1.y < xCoeff*e2.x + yCoeff*e2.y; }); Point ret; ret.x = 0; ret.y = 0; for(auto e : v){ int 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 print(Point& p){ cout << p.x << ' ' << p.y << '\n'; for(auto e : p.v) cout << e.a << ' ' << e.b << '\n'; } Point best; void rek(Point& a, Point& b){ Point 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(novi.x * novi.y < best.x * best.y) best = novi; rek(a, novi); rek(novi, b); } int main(){ srand(time(0)); cin >> n >> m; for(int i = 0; i < m; i++){ Edge e; cin >> e.a >> e.b >> e.x >> e.y; edges.push_back(e); } Point minX = solve(1, 0); Point minY = solve(0, 1); best = minX; if(best.x * best.y < minY.x * minY.y) best = minY; if(!eq(minX, minY)) rek(minX, minY); print(best); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...