Submission #537017

#	Time	Username	Problem	Language	Result	Execution time	Memory
537017		cig32	timeismoney (balkan11_timeismoney)	C++17	60 / 100	1400 ms	1740 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e3 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}

struct edge {
  int to, a, b;
};

vector<edge> adj[MAXN];
int n, m;
map<pair<int, int>, bool> oh;

struct answer {
  int a, b;
  vector<pair<int, int> > soln;
};

answer calc(int st) {
  int A = 0, B = 0;
  bool intree[n];
  for(int i=0; i<n; i++) intree[i] = 0;
  intree[st] = 1;
 
  vector<pair<int, int> > edges;
  for(int i=1; i<n; i++) {
    int mi = 1e18, id, opt_a, opt_b, opt_fr;
    for(int j=0; j<n; j++) {
      if(intree[j]) {
        for(int k=0; k<adj[j].size(); k++) {
          if(intree[adj[j][k].to]) continue;
          int cost = (A + adj[j][k].a) * (B + adj[j][k].b);
          if(cost < mi) {
            mi = cost;
            id = adj[j][k].to;
            opt_a = adj[j][k].a;
            opt_b = adj[j][k].b;
            opt_fr = j;
          }
        }
      }
    }
    if(oh[{opt_fr, id}]) edges.push_back({opt_fr, id});
    else edges.push_back({id, opt_fr});
    intree[id] = 1;
    A += opt_a;
    B += opt_b;
  }

  return {A, B, edges};
}
void solve(int tc) {
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    oh[{x, y}] = 1;
    adj[x].push_back({y, a, b});
    adj[y].push_back({x, a, b});
  }

  int ans = 1e18;
  int A, B;
  vector<pair<int, int> > edges;
  for(int i=0; i<n; i++) {
    answer ok = calc(i);
    if(ok.a * ok.b < ans) {
      A = ok.a, B = ok.b;
      ans = ok.a * ok.b;
      edges = ok.soln;
    }
  }
  
  cout << A << " " << B << "\n";
  for(pair<int, int> x: edges) cout << x.first << ' ' << x.second << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
3 3
0 1 1 3
1 2 4 1
0 2 3 1
*/

Compilation message (stderr)

timeismoney.cpp: In function 'answer calc(long long int)':
timeismoney.cpp:36:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int k=0; k<adj[j].size(); k++) {
      |                      ~^~~~~~~~~~~~~~
timeismoney.cpp:51:16: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     intree[id] = 1;
      |     ~~~~~~~~~~~^~~
timeismoney.cpp:53:7: warning: 'opt_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |     B += opt_b;
      |     ~~^~~~~~~~
timeismoney.cpp:52:7: warning: 'opt_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     A += opt_a;
      |     ~~^~~~~~~~

• Subtask 1: 60 / 100