oj.uz

답안 #537017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537017 2022-03-14T09:40:51 Z cig32 시간이 돈 (balkan11_timeismoney) C++17
60 / 100
 1400 ms 1740 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 392 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 16 ms 340 KB Output is correct
6 Correct 54 ms 340 KB Output is correct
7 Correct 281 ms 640 KB Output is correct
8 Correct 1376 ms 1620 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Incorrect 16 ms 424 KB Output isn't correct
15 Incorrect 50 ms 340 KB Output isn't correct
16 Incorrect 288 ms 648 KB Output isn't correct
17 Incorrect 271 ms 636 KB Output isn't correct
18 Incorrect 267 ms 632 KB Output isn't correct
19 Incorrect 1360 ms 1732 KB Output isn't correct
20 Incorrect 1400 ms 1740 KB Output isn't correct