Submission #468024

#	Time	Username	Problem	Language	Result	Execution time	Memory
468024		czhang2718	timeismoney (balkan11_timeismoney)	C++17	90 / 100	903 ms	576 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;

#define nl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

int n, m;
pair<long long, pii> ans;
vi edges;
const int N=200;
const int M=10000;
int u[M], v[M], t[M], c[M];
int par[N];
pii b;

int find(int x){
  if(par[x]==x) return x;
  return par[x]=find(par[x]);
}

bool join(int x, int y){
  int a=find(x);
  int b=find(y);
  if(a==b) return 0;
  par[a]=b;
  return 1; 
}

bool comp(int i, int j){
  return (ll)b.f*t[i]+b.s*c[i]<(ll)b.f*t[j]+b.s*c[j];
  // if(t[i]!=t[j]) return t[i]<t[j]; // should be useless..
  // return c[i]<c[j];
}

pii get_min(pii bb){
  b=bb;
  sort(edges.begin(), edges.end(), comp);
  for(int i=0; i<n; i++) par[i]=i;
  pii ret={0, 0};
  for(int e:edges){
    if(join(u[e], v[e])){
      ret.f+=t[e];
      ret.s+=c[e];
    }
  }
  return ret;
}

void search(pii l, pii r){
  pii bb={-(r.s-l.s), r.f-l.f};
  pii m=get_min(bb);
  ans=min(ans, {m.f*m.s, bb});
  if((ll)b.f*m.f+b.s*m.s==(ll)b.f*l.f+b.s*l.s) return;
  search(l, m);
  search(m, r);
}

void answer(pii bb){
  b=bb;
  sort(edges.begin(), edges.end(), comp);
  for(int i=0; i<n; i++) par[i]=i;
  pii ret={0, 0};
  vi use;
  for(int e:edges){
    if(join(u[e], v[e])){
      ret.f+=t[e];
      ret.s+=c[e];
      use.pb(e);
    }
  }
  cout << ret.f << " " << ret.s << nl;
  for(int i:use) cout << u[i] << " " << v[i] << nl; 
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  cin >> n >> m;
  for(int i=0; i<m; i++){
    cin >> u[i] >> v[i] >> t[i] >> c[i];
    edges.pb(i);
  }

  pii l=get_min({1, 0});
  pii r=get_min({0, 1});
  ans=min(mp(l.f*l.s, mp(1, 0)), mp(r.f*r.s, mp(0, 1)));

  search(l, r);
  answer(ans.s);
}
// n=200*256
// # CH vertices <= n^(3/4)
// ~ 4e7

• Subtask 1: 90 / 100