oj.uz

Submission #467994

# Submission time Handle Problem Language Result Execution time Memory
467994 2021-08-25T20:08:10 Z czhang2718 timeismoney (balkan11_timeismoney) C++14
90 / 100
 840 ms 668 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;

int n, m;
pair<int, 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 b.f*t[i]+b.s*c[i]<b.f*t[j]+b.s*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(b.f*m.f+b.s*m.s==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);
  // cout << "best slope " << ans.s.f << " " << ans.s.s << nl;
  answer(ans.s);
}
// n=200*256
// # CH vertices <= n^(3/4)
// ~ 4e7

Subtask #1
90.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 1 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 668 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 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 Incorrect 4 ms 332 KB Output isn't correct
16 Correct 89 ms 360 KB Output is correct
17 Correct 95 ms 352 KB Output is correct
18 Correct 89 ms 332 KB Output is correct
19 Correct 830 ms 644 KB Output is correct
20 Incorrect 840 ms 644 KB Output isn't correct