Submission #244524

#	Time	Username	Problem	Language	Result	Execution time	Memory
244524		Nightlight	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	251 ms	1548 KiB

timeismoney

#include <bits/stdc++.h>
#define pii pair<long double, int>
using namespace std;

int N, M, sumA, sumB;
int U[10005], V[10005];
long double T[10005], C[10005];
int stora[205][205];
int storb[205][205];
int par[205];
pii edge[10005];
bitset<10005> used;
long double MAX = 1e6;
//sumA * sumB <= K
//sumA <= K / sumB
//sumA - K / sumB <= 0

int findpar(int u) {
  return par[u] == u ? u : par[u] = findpar(par[u]);
}

int val(long double mid) {
  for(int i = 0; i < N; i++) par[i] = i;
  for(int i = 1; i <= M; i++) {
    edge[i] = make_pair(T[i] * mid + C[i] * (MAX - mid), i);
  }
  used = 0;
  sumA = 0, sumB = 0;
  sort(edge + 1, edge + M + 1);
  int u, v, id;
  long double cur;
  for(int i = 1; i <= M; i++) {
    id = edge[i].second;
    u = U[id], v = V[id];
    u = findpar(u), v = findpar(v);
    if(u == v) continue;
    par[v] = u;
    sumA += T[id];
    sumB += C[id];
    used[id] = 1;
  }
  return sumA * sumB;
}

int main() {
  scanf("%d %d", &N, &M);
  for(int i = 1; i <= M; i++) {
    cin >> U[i] >> V[i] >> T[i] >> C[i];
    stora[U[i]][V[i]] = T[i];
    storb[U[i]][V[i]] = C[i];
  }
  long double l = 1, r = MAX - 1;
  while(r - l > 1e-6) {
    long double m1 = l + (r - l) / 3;
    long double m2 = r - (r - l) / 3;
    if(val(m1) < val(m2)) {
      r = m2;
    }else {
      l = m1;
    }
  }
  val(l);
  int u, v;
  long double now;
  printf("%d %d\n", sumA, sumB);
  for(int i = 1; i <= M; i++) {
    if(used[i] == 0) continue;
    printf("%d %d\n", U[i], V[i]);
  }
  cin >> N;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int val(long double)':
timeismoney.cpp:31:15: warning: unused variable 'cur' [-Wunused-variable]
   long double cur;
               ^~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:63:7: warning: unused variable 'u' [-Wunused-variable]
   int u, v;
       ^
timeismoney.cpp:63:10: warning: unused variable 'v' [-Wunused-variable]
   int u, v;
          ^
timeismoney.cpp:64:15: warning: unused variable 'now' [-Wunused-variable]
   long double now;
               ^~~
timeismoney.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100