oj.uz

Submission #468025

# Submission time Handle Problem Language Result Execution time Memory
468025 2021-08-25T22:33:30 Z czhang2718 timeismoney (balkan11_timeismoney) C++17
100 / 100
 983 ms 560 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];
  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 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 460 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 7 ms 336 KB Output is correct
15 Correct 4 ms 204 KB Output is correct
16 Correct 100 ms 360 KB Output is correct
17 Correct 101 ms 332 KB Output is correct
18 Correct 114 ms 332 KB Output is correct
19 Correct 943 ms 552 KB Output is correct
20 Correct 983 ms 560 KB Output is correct