Submission #47625

#	Time	Username	Problem	Language	Result	Execution time	Memory
47625		tincamatei	timeismoney (balkan11_timeismoney)	C++14	100 / 100	769 ms	892 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 255;
const int MAX_M = 10000;

struct Muchie {
  int a, b, c, d;
  int cost;
  bool inapm;
}mc[MAX_M];

bool cmp(Muchie a, Muchie b) {
  return a.cost < b.cost;
}

int sefu[MAX_N];

int myfind(int x) {
  if(x == sefu[x])
    return x;
  else {
    sefu[x] = myfind(sefu[x]);
    return sefu[x];
  }
}

void myunion(int a, int b) {
  int sa = myfind(a), sb = myfind(b);
  if(sa != sb)
    sefu[sa] = sb;
}

bool ccw(pair<int, int>a, pair<int, int>b, pair<int, int>c) {
  return (long long)a.first * b.second +
         (long long)b.first * c.second +
         (long long)c.first * a.second -
         (long long)a.first * c.second -
         (long long)b.first * a.second -
         (long long)c.first * b.second > 0;
}

pair<int, int> apm(int n, int m, int alfa, int beta) {
  int rem = n - 1;
  pair<int, int> rez = make_pair(0, 0);
  for(int i = 0; i < n; ++i)
    sefu[i] = i;
  for(int i = 0; i < m; ++i) {
    mc[i].cost = mc[i].c * alfa + mc[i].d * beta;
    mc[i].inapm = false;
  }
  sort(mc, mc + m, cmp);
  for(int i = 0; i < m; ++i) {
    if(myfind(mc[i].a) != myfind(mc[i].b)) {
      rez.first += mc[i].c;
      rez.second += mc[i].d;
      myunion(mc[i].a, mc[i].b);
      mc[i].inapm = true;
      --rem;
      if(rem == 0)
        return rez;
    }
  }
  return rez;
}

long long costfinal = 1000000000000000000LL;
pair<int, int> coef;
void solve(int n, int m, pair<int, int>st, pair<int, int>dr) {
  pair<int, int> mid = apm(n, m, st.second - dr.second, dr.first - st.first);
  if((long long)mid.first * mid.second < costfinal) {
    costfinal = (long long)mid.first * mid.second;
    coef.first = st.second - dr.second;
    coef.second = dr.first - st.first;
  }
  if(ccw(st, mid, dr)) {
    solve(n, m, st, mid);
    solve(n, m, mid, dr);
  }
}

int main() {
#ifdef HOME
  FILE *fin = fopen("timeismoney.in", "r");
  FILE *fout = fopen("timeismoney.out", "w");
#else
  FILE *fin = stdin;
  FILE *fout = stdout;
#endif
  int n, m;
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 0; i < m; ++i)
    fscanf(fin, "%d%d%d%d", &mc[i].a, &mc[i].b, &mc[i].c, &mc[i].d);

  pair<int, int>st, dr, xd;
  st = apm(n, m, 1, 0);
  dr = apm(n, m, 0, 1);
  if((long long)st.first * st.second < costfinal) {
    costfinal = (long long)st.first * st.second;
    coef.first = 1;
    coef.second = 0;
  }
  if((long long)dr.first * dr.second < costfinal) {
    costfinal = (long long)dr.first * dr.second;
    coef.first = 0;
    coef.second = 1;
  }

  solve(n, m, st, dr);

  xd = apm(n, m, coef.first, coef.second);

  fprintf(fout, "%d %d\n", xd.first, xd.second);
  for(int i = 0; i < m; ++i)
    if(mc[i].inapm)
      fprintf(fout, "%d %d\n", mc[i].a, mc[i].b);

#ifdef HOME
  fclose(fin);
  fclose(fout);
#endif // HOME
  return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:92:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &n, &m);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:94:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d%d%d", &mc[i].a, &mc[i].b, &mc[i].c, &mc[i].d);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100