Submission #1312804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312804		cadmiumsky	timeismoney (balkan11_timeismoney)	C++20	50 / 100	2098 ms	126236 KiB

timeismoney

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

using tiii = tuple<int, int, int, int>;
//using tii = tuple<int, int, int>;
using pii = pair<int, int>;


namespace DSU {
   const int nmax = 2e5 + 5;
   int dsu[nmax];
   void init(int N) {
      for(int i = 0; i <= N; i++) dsu[i] = i;
   }
   int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
   void unite(int x, int y) {
      dsu[f(x)] = f(y);
   }
};

int N;
vector<tiii> edges;
vector<pii> cand;


pair<int, int> tangentLine(int a, int b) {
   sort(all(edges), [&](auto x, auto y) { return get<2>(x) * a + get<3>(x) * b < get<2>(y) * a + get<3>(y) * b; });
   cand.clear();
   
   int X = 0, Y = 0;
   DSU::init(N);
   for(auto [u, v, x, y] : edges) {
      if(DSU::f(u) == DSU::f(v));
      else X += x, Y += y, cand.emplace_back(u, v), DSU::unite(u, v);
   }
   return pii{X, Y};
}

ll best = 2e10;
int a, b;

void upd(pii x, int ma, int mb) {
   if(best > (ll)x.first * x.second) {
      best = (ll)x.first * x.second;
      a = ma;
      b = mb;
   }
}

void divide(pii l, pii r) {
   int ma = -(l.second - r.second), mb = l.first - r.first;
   //ma *= -1, mb *= -1;
   //cerr << l.first << ' ' << l.second << '\n';
   //cerr << r.first << ' ' << r.second << '\n';

   auto x = tangentLine(ma, mb);
   //cerr << x.first << ' ' << x.second << '\n';
   if(x == l || x == r) return;
   
   upd(x, ma, mb);
      
   divide(l, x);
   divide(x, r);
}

signed main() {
   int m;
   //...
   cin >> N >> m;
   edges.resize(m);
   for(auto &[a, b, c, d] : edges)
      cin >> a >> b >> c >> d;
   
   
   divide(tangentLine(0, 1), tangentLine(1, 0));
   upd(tangentLine(0, 1), 0, 1);
   upd(tangentLine(1, 0), 1, 0);
   
   auto [x, y] = tangentLine(a, b);
   
   cout << x << ' ' << y << '\n';
   for(auto [u, v] : cand) cout << u << ' ' << v << '\n';
}

• Subtask 1: 50 / 100