Submission #1194811

#TimeUsernameProblemLanguageResultExecution timeMemory
1194811AliMark71timeismoney (balkan11_timeismoney)C++20
100 / 100
1892 ms1640 KiB
// // main.cpp // GeneralCompetitiveProgramming // // Created by Ali AlSalman on 12/07/2023. // #include <bits/stdc++.h> //#define INTERACTIVE //#define TESTCASES #ifndef INTERACTIVE #define endl '\n' #endif template<typename T> using vec = std::vector<T>; using namespace std; typedef vec<pair<int, int>> mst_t; struct mst_value_t { long long cost, time; bool operator ==(const mst_value_t &other) const { return cost == other.cost && time == other.time; } }; struct mst_query_t { mst_t mst; mst_value_t value; }; bool mask = true; vec<bool> vis; vec<vec<array<int, 3>>> adj; mst_query_t mst(long long a, long long b, bool construct = false) { mst_t tree; long long sum_c = 0, sum_t = 0; auto cmp_maker = [](long long a, long long b) -> function<bool(array<long long, 4>, array<long long, 4>)>{ return [a, b](array<long long, 4> lhs, array<long long, 4> rhs) -> bool { return a * lhs[2] + b * lhs[3] > a * rhs[2] + b * rhs[3]; }; }; priority_queue< array<long long, 4>, vec<array<long long, 4>>, decltype(cmp_maker(a, b)) > q(cmp_maker(a, b)); q.push({0, -1, 0, 0}); while (!q.empty()) { auto [u, v, _c, _t] = q.top(); q.pop(); if (vis[u] == mask) continue; vis[u] = !vis[u]; if (construct && 0 <= u && 0 <= v) tree.push_back({u, v}); sum_c += _c; sum_t += _t; for (auto [c, c_c, c_t] : adj[u]) if (vis[c] != mask) { q.push({c, u, c_c, c_t}); } } mask = !mask; return {tree, {sum_c, sum_t}}; } struct mst_producer_t { long long cost_factor, time_factor; }; struct cnvx_t { mst_producer_t producer; mst_value_t mst_value; }; cnvx_t cnvx(cnvx_t a, cnvx_t b) { auto min_p = [](cnvx_t a, cnvx_t b) { if (a.mst_value.cost * a.mst_value.time <= b.mst_value.cost * b.mst_value.time) return a; return b; }; cnvx_t p = { { a.mst_value.time - b.mst_value.time, b.mst_value.cost - a.mst_value.cost }, mst(a.mst_value.time - b.mst_value.time, b.mst_value.cost - a.mst_value.cost).value }; if (p.mst_value == a.mst_value || p.mst_value == b.mst_value) return min_p(a, b); return min_p(cnvx(a, p), cnvx(p, b)); } void solve() { int n, m; cin>>n>>m; vis.resize(n); adj.resize(n); while (m--) { int a, b, c, d; cin>>a>>b>>c>>d; adj[a].push_back({b, c, d}); adj[b].push_back({a, c, d}); } auto c_point = mst(1, 0).value; auto t_point = mst(0, 1).value; auto opt = cnvx({ { 1, 0 }, c_point }, { { 0, 1 }, t_point }); cout<<opt.mst_value.cost<<" "<<opt.mst_value.time<<endl; for (auto [u, v] : mst(opt.producer.cost_factor, opt.producer.time_factor, true).mst) { cout<<u<<" "<<v<<endl; } } int main() { #ifndef INTERACTIVE ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #endif int t = 1; #ifdef TESTCASES cin>>t; #endif while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...