Submission #1003003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003003		AdamGS	timeismoney (balkan11_timeismoney)	C++17	100 / 100	900 ms	1816 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e4+7;
pair<ll,pair<ll,ll>>best={INF, {INF, INF}};
pair<pair<int,int>,pair<ll,ll>>T[LIM];
vector<pair<int,int>>wyn;
int F[LIM], n, m;
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
  if(fnd(a)==fnd(b)) return false;
  F[fnd(b)]=fnd(a);
  return true;
}
pair<ll,ll>cnt(ll a, ll b) {
  wyn.clear();
  vector<pair<pair<ll,ll>,pair<ll,ll>>>kraw;
  rep(i, m) kraw.pb({{a*T[i].nd.st+b*T[i].nd.nd, i}, T[i].st});
  sort(all(kraw));
  rep(i, n) F[i]=i;
  pair<ll,ll>ans={0, 0};
  for(auto i : kraw) if(uni(i.nd.st, i.nd.nd)) {
    ans.st+=T[i.st.nd].nd.st;
    ans.nd+=T[i.st.nd].nd.nd;
    wyn.pb(i.nd);
  }
  best=min(best, {ans.st*ans.nd, {a, b}});
  return ans;
}
void solve(pair<ll,ll>a, pair<ll,ll>b) {
  ll ans=min(a.st*a.nd, b.st*b.nd);
  pair<ll,ll>c=cnt(a.nd-b.nd, b.st-a.st);
  if(c==a || c==b) return;
  solve(a, c);
  solve(c, b);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  rep(i, m) cin >> T[i].st.st >> T[i].st.nd >> T[i].nd.st >> T[i].nd.nd;
  solve(cnt(1, 0), cnt(0, 1));
  cout << cnt(best.nd.st, best.nd.nd).st << " " << cnt(best.nd.st, best.nd.nd).nd << '\n';
  for(auto i : wyn) cout << i.st << " " << i.nd << '\n';
}

Compilation message (stderr)

timeismoney.cpp: In function 'void solve(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
timeismoney.cpp:41:6: warning: unused variable 'ans' [-Wunused-variable]
   41 |   ll ans=min(a.st*a.nd, b.st*b.nd);
      |      ^~~

• Subtask 1: 100 / 100