Submission #1237873

#TimeUsernameProblemLanguageResultExecution timeMemory
1237873Icelasttimeismoney (balkan11_timeismoney)C++20
0 / 100
1 ms328 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct DSU{ int n; vector<int> pa, sz; DSU(int n) : n(n){ pa.resize(n+1); sz.resize(n+1, 1); for(int i = 0; i <= n; i++){ pa[i] = i; } }; int find(int x){ while(x != pa[x]){ x = pa[x] = pa[pa[x]]; } return x; } bool same(int x, int y){ return find(x) == find(y); } bool merge(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(sz[x] < sz[y]) swap(x, y); pa[y] = x; sz[x] += sz[y]; return true; } int size(int x){ return sz[find(x)]; } }; struct edge{ int u, v, t, c; }; struct mst{ ll SumTime, SumMoney; vector<pair<int, int>> e; }; void solve(){ int n, m; cin >> n >> m; vector<edge> edges(m+1); for(int i = 1; i <= m; i++){ int u, v, t, c; cin >> u >> v >> t >> c; edges[i] = {u, v, t, c}; } //https://dmoj.ca/problem/bkoi11p5/editorial vector<mst> Convex_Hull; auto get_mst = [&](ll a, ll b) -> mst{ // get the mst with minimum at + bc (in other words slope -a/b) mst res; res.SumTime = 0, res.SumMoney = 0; vector<edge> e = edges; sort(e.begin()+1, e.end(), [&](edge x, edge y){return x.t*a + x.c*b < y.t*a + y.c*b;}); DSU dsu(n+1); for(int i = 1; i <= m; i++){ if(dsu.merge(e[i].u, e[i].v)){ res.SumTime += e[i].t; res.SumMoney += e[i].c; res.e.push_back({e[i].u, e[i].v}); } } return res; }; map<pair<ll, ll>, int> mp; auto f = [&](auto f, mst x, mst y) -> void{ ll b = x.SumTime - y.SumTime; ll a = y.SumMoney - x.SumMoney; mst z = get_mst(a, b); if(mp[{z.SumTime, z.SumMoney}]){ return; } mp[{z.SumTime, z.SumMoney}] = 1; Convex_Hull.push_back(z); f(f, x, z); f(f, z, y); }; Convex_Hull.push_back(get_mst(0, 1)); Convex_Hull.push_back(get_mst(1, 0)); f(f, Convex_Hull[0], Convex_Hull[1]); auto g = [&](mst x) -> ll{ return x.SumTime*x.SumMoney; }; mst best; best.SumTime = 1e9, best.SumMoney = 1e9; for(auto it : Convex_Hull){ if(g(it) < g(best)){ best = it; } } cout << best.SumTime << " " << best.SumMoney << "\n"; for(auto it : best.e){ cout << it.first << " " << it.second << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("timeismoney.in", "r", stdin); freopen("timeismoney.out", "w", stdout); solve(); }

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen("timeismoney.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     freopen("timeismoney.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...