oj.uz

Submission #468023

# Submission time Handle Problem Language Result Execution time Memory
468023 2021-08-25T22:32:32 Z czhang2718 timeismoney (balkan11_timeismoney) C++17
100 / 100
 994 ms 572 KB 
#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){
  if((ll)b.f*t[i]+b.s*c[i]!=(ll)b.f*t[j]+b.s*c[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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 7 ms 572 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 97 ms 356 KB Output is correct
17 Correct 103 ms 356 KB Output is correct
18 Correct 95 ms 332 KB Output is correct
19 Correct 922 ms 460 KB Output is correct
20 Correct 994 ms 556 KB Output is correct