Submission #1010542

#TimeUsernameProblemLanguageResultExecution timeMemory
1010542vjudge1timeismoney (balkan11_timeismoney)C++17
50 / 100
2102 ms65536 KiB
// ^^ // <{:3 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native") //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC optimize("O3") #include<bits/stdc++.h> //#define int long signed long int #define ld long double using namespace std; const int maxn = 202; vector<tuple<ld, ld, int, int>> edges; // c t x y pair<int, ld> ans; // val, k int p[maxn]; int n, m; inline void rt() { for(int i = 0; i <= n; ++i) p[i] = i; } int f(int x) { if(p[x] == x) return x; return p[x] = f(p[x]); } inline void u(int x, int y) { x = f(x); y = f(y); if(x == y) return; p[x] = y; } pair<int, int> mst(ld k) { vector<tuple<ld, ld, ld, int, int>> v; rt(); for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y); sort(v.begin(), v.end()); pair<int, int> ret(0, 0); for(auto [val, c, t, x, y] : v) { if(f(x) != f(y)) { ret.first += c; ret.second += t; u(x, y); } } return ret; } void rec(ld x1, ld y1, ld x2, ld y2) { if(x1 == x2) return; ld k = (y1 - y2) / (x1 - x2); ld c = y1 - (k * x1); pair<int, int> novi = mst(-k); ld y = (k*novi.first) + c; //cout << novi.first << " " << novi.second << " " << k << " dbdb\n"; if(novi.second >= y) return; if(novi.first * novi.second < ans.first) { ans.first = novi.first * novi.second; ans.second = k; } rec(x1, y1, novi.first, novi.second); rec(x2, y2, novi.first, novi.second); } signed main() { cin.tie(NULL)->sync_with_stdio(false); ans = {1e9, 0}; cin >> n >> m; for(int i = 0; i < m; ++i) { ld t, c; int x, y; cin >> x >> y >> t >> c; edges.emplace_back(t, c, x, y); } rt(); vector<pair<int, int>> minte, mince; sort(edges.begin(), edges.end()); pair<int, int> mint(0, 0); for(auto &[t, c, x, y] : edges) { int xtr = f(x), ytr = f(y); if(xtr != ytr) { mint.first += c; mint.second += t; minte.emplace_back(x, y); u(xtr, ytr); } swap(t, c); } rt(); sort(edges.begin(), edges.end()); pair<int, int> minc(0, 0); for(auto &[c, t, x, y] : edges) { int xtr = f(x), ytr = f(y); if(xtr != ytr) { minc.first += c; minc.second += t; mince.emplace_back(x, y); u(xtr, ytr); } } rec(minc.first, minc.second, mint.first, mint.second); if(minc.first * minc.second < ans.first) { swap(minc.first, minc.second); cout << minc.first << " " << minc.second << "\n"; for(auto [x, y] : mince) cout << x << " " << y << "\n"; return 0; } if(mint.first * mint.second < ans.first) { swap(mint.first, mint.second); cout << mint.first << " " << mint.second << "\n"; for(auto [x, y] : minte) cout << x << " " << y << "\n"; return 0; } rt(); ld k = -ans.second; vector<tuple<ld, ld, ld, int, int>> v; for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y); sort(v.begin(), v.end()); pair<int, int> ret(0, 0); vector<pair<int, int>> ansedge; for(auto [val, c, t, x, y] : v) { if(f(x) != f(y)) { ret.first += c; ret.second += t; u(x, y); ansedge.emplace_back(x, y); } } swap(ret.first, ret.second); cout << ret.first << " " << ret.second << "\n"; for(auto [x, y] : ansedge) cout << x << " " << y << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...