Submission #1029871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029871		AverageAmogusEnjoyer	timeismoney (balkan11_timeismoney)	C++17	60 / 100	15 ms	768 KiB

timeismoney

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());

int rng() {
    return abs((int)mrand());
}

// Current challenge: finish CSES problemset!!

struct DSU {
	vector<int> e;
	int ccs;
    DSU(int n) { ccs = n; e = vector<int>(n, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) { return 0; }
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
        ccs--;
        return 1;
	}
};

void solve() {
    int n,m;
    cin >> n >> m;
    vector<array<int,4>> edges(m);
    for (auto &[x,y,t,c]: edges) {
        cin >> x >> y >> t >> c;
    }
    int T = 0, C = 0;
    constexpr int inf = 1e9;
    DSU dsu(n);
    vector<pair<int,int>> ans;
    for (int _=1;_<n;_++) {
        int M = inf;
        int idx = -1;
        int p = -1;
        for (auto &[x,y,t,c]: edges) {
            ++p;
            if (dsu.same_set(x,y)) { continue; }
            if (cmin(M,(T + t) * (C + c))) {
                idx = p;
            }
        }
        assert(idx != -1);
        ans.emplace_back(edges[idx][0],edges[idx][1]);
        dsu.unite(edges[idx][0],edges[idx][1]);
        T += edges[idx][2];
        C += edges[idx][3];
    }
    cout << T << " " << C << "\n";
    for (auto &[x,y]: ans) {
        cout << x << " " << y << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int _t = 1;
    // cin >> _t;
    for (int i=1;i<=_t;i++) {
        solve();
    }
}

• Subtask 1: 60 / 100