oj.uz

Submission #1003003

# Submission time Handle Problem Language Result Execution time Memory
1003003 2024-06-20T00:40:15 Z AdamGS timeismoney (balkan11_timeismoney) C++17
100 / 100
 900 ms 1816 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 8 ms 1700 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 77 ms 656 KB Output is correct
17 Correct 81 ms 604 KB Output is correct
18 Correct 76 ms 600 KB Output is correct
19 Correct 825 ms 1816 KB Output is correct
20 Correct 900 ms 1540 KB Output is correct