oj.uz

Submission #1029871

# Submission time Handle Problem Language Result Execution time Memory
1029871 2024-07-21T12:56:05 Z AverageAmogusEnjoyer timeismoney (balkan11_timeismoney) C++17
60 / 100
 15 ms 768 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 15 ms 768 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Incorrect 3 ms 348 KB Output isn't correct
17 Incorrect 2 ms 476 KB Output isn't correct
18 Incorrect 2 ms 720 KB Output isn't correct
19 Incorrect 15 ms 600 KB Output isn't correct
20 Incorrect 12 ms 604 KB Output isn't correct