Submission #537016

# Submission time Handle Problem Language Result Execution time Memory
537016 2022-03-14T09:36:26 Z cig32 timeismoney (balkan11_timeismoney) C++17
50 / 100
17 ms 1592 KB
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 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;
};
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  vector<edge> adj[n];
  map<pair<int, int>, bool> oh;
  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 A = 0, B = 0;
  bool intree[n];
  for(int i=0; i<n; i++) intree[i] = 0;
  intree[rnd(0, n - 1)] = 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;
  }
  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

timeismoney.cpp: In function 'void solve(long long int)':
timeismoney.cpp:37:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int k=0; k<adj[j].size(); k++) {
      |                      ~^~~~~~~~~~~~~~
timeismoney.cpp:52:16: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     intree[id] = 1;
      |     ~~~~~~~~~~~^~~
timeismoney.cpp:54:7: warning: 'opt_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     B += opt_b;
      |     ~~^~~~~~~~
timeismoney.cpp:53:7: warning: 'opt_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |     A += opt_a;
      |     ~~^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 14 ms 1592 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Incorrect 3 ms 596 KB Output isn't correct
17 Incorrect 3 ms 612 KB Output isn't correct
18 Incorrect 3 ms 548 KB Output isn't correct
19 Incorrect 14 ms 1592 KB Output isn't correct
20 Incorrect 17 ms 1592 KB Output isn't correct