oj.uz

Submission #47619

# Submission time Handle Problem Language Result Execution time Memory
47619 2018-05-05T21:34:49 Z tincamatei timeismoney (balkan11_timeismoney) C++14
0 / 100
 2 ms 1028 KB 
#include <bits/stdc++.h>

#define HOME

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;
}

pair<int, int> apm(int n, int m, int alfa, int beta) {
  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;
    }
  }
  return rez;
}

long long costfinal = 1000000000000000000LL;
pair<int, int> coef;

map<pair<int, int>, bool> puncte;

void solve(int n, int m, pair<int, int>st, pair<int, int>dr) {
  pair<int, int> mid = apm(n, m, st.first - dr.first, dr.second - st.second);
  if((long long)mid.first * mid.second < costfinal) {
    costfinal = (long long)mid.first * mid.second;
    coef.first = st.first - dr.first;
    coef.second = dr.second - st.second;
  }
  if(!puncte[mid]) {
    puncte[mid] = true;
    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, 0, 1);
  dr = apm(n, m, 1, 0);
  if((long long)st.first * st.second < costfinal) {
    costfinal = (long long)st.first * st.second;
    coef.first = 0;
    coef.second = 1;
  }
  if((long long)dr.first * dr.second < costfinal) {
    costfinal = (long long)dr.first * dr.second;
    coef.first = 1;
    coef.second = 0;
  }

  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

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:85: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:87: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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 2 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 2 ms 1020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 2 ms 1028 KB Execution killed with signal 11 (could be triggered by violating memory limits)