oj.uz

Submission #468021

# Submission time Handle Problem Language Result Execution time Memory
468021 2021-08-25T22:26:13 Z czhang2718 timeismoney (balkan11_timeismoney) C++14
100 / 100
 1070 ms 716 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 1 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 716 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 5 ms 320 KB Output is correct
16 Correct 101 ms 332 KB Output is correct
17 Correct 105 ms 384 KB Output is correct
18 Correct 98 ms 332 KB Output is correct
19 Correct 951 ms 708 KB Output is correct
20 Correct 1070 ms 716 KB Output is correct