Submission #638057

#	Time	Username	Problem	Language	Result	Execution time	Memory
638057		MohamedFaresNebili	timeismoney (balkan11_timeismoney)	C++14	100 / 100	602 ms	1072 KiB

timeismoney

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
            using namespace std;
            using ll = long long;
 
            #define int ll
 
            int N, M, P[205];
            vector<array<int, 5>> E;
 
            int findSet(int v) {
                if(P[v] == v) return v;
                return P[v] = findSet(P[v]);
            }
            int unionSet(int u, int v) {
                u = findSet(u), v = findSet(v);
                if(u == v) return 0;
                P[u] = v;
                return 1;
            }
 
            pair<pair<int, int>, vector<int>> solve(vector<int> W) {
                sort(E.begin(), E.end(),
                     [&](array<int, 5> A, array<int, 5> B) {
                     return W[A[4]] < W[B[4]];
                });
                for(int l = 0; l < N; l++) P[l] = l;
                int A = 0, B = 0; vector<int> mst;
                for(auto u : E) {
                    if(unionSet(u[0], u[1])) {
                        A += u[2], B += u[3];
                        mst.push_back(u[4]);
                    }
                }
                return {{A, B}, mst};
            }
 
            int area(pair<int, int> A, pair<int, int> B, pair<int, int> C) {
                pair<int, int> U = {B.first - A.first, B.second - A.second};
                pair<int, int> V = {C.first - A.first, C.second - A.second};
                return U.first * V.second - U.second * V.first;
            }
 
            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 0; l < M; l++) {
                    int U, V, T, C; cin >> U >> V >> T >> C;
                    E.push_back({U, V, T, C, l});
                }
                vector<int> res, W(M);
                pair<int, int> ans = {1e8, 1e8};
                for(int l = 0; l < M; l++)
                    W[E[l][4]] = E[l][2];
                pair<int, int> A, B, C; vector<int> cur;
                tie(A, res) = solve(W); ans = A;
                for(int l = 0; l < M; l++)
                    W[E[l][4]] = E[l][3];
                tie(B, cur) = solve(W);
                if(B.first * B.second < A.first * A.second) {
                    ans = B; res = cur;
                }
                vector<array<pair<int, int>, 2>> ST;
                ST.push_back({A, B});
                while(!ST.empty()) {
                    A = ST.back()[0]; B = ST.back()[1]; ST.pop_back();
                    for(int l = 0; l < M; l++)
                        W[E[l][4]] = E[l][3] * (B.first - A.first)
                        - E[l][2] * (B.second - A.second);
                    tie(C, cur) = solve(W);
                    if(C.first * C.second < ans.first * ans.second) {
                        ans = C; res = cur;
                    }
                    if(area(A, B, C) >= 0) continue;
                    ST.push_back({A, C}); ST.push_back({C, B});
                }
                cout << ans.first << " " << ans.second << "\n";
                sort(E.begin(), E.end(),
                     [&](array<int, 5> A, array<int, 5> B) {
                     return A[4] < B[4];
                });
                for(auto u : res) cout << E[u][0] << " " << E[u][1] << "\n";
                return 0;
            }
 

• Subtask 1: 100 / 100