답안 #536964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536964 2022-03-14T08:19:41 Z cig32 시간이 돈 (balkan11_timeismoney) C++17
55 / 100
15 ms 1736 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];
  intree[0] = 1;
  for(int i=1; i<n; i++) intree[i] = 0;
  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);
}

Compilation message

timeismoney.cpp: In function 'void solve(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;
      |     ~~^~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 15 ms 1620 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Incorrect 5 ms 596 KB Output isn't correct
17 Incorrect 3 ms 596 KB Output isn't correct
18 Incorrect 3 ms 576 KB Output isn't correct
19 Incorrect 14 ms 1732 KB Output isn't correct
20 Incorrect 13 ms 1736 KB Output isn't correct