結果
| 問題 | No.1316 Maximum Minimum Spanning Tree |
| ユーザー |
 opt
|
| 提出日時 | 2020-11-28 15:40:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 1,566 bytes |
| コンパイル時間 | 7,520 ms |
| コンパイル使用メモリ | 336,292 KB |
| 実行使用メモリ | 813,952 KB |
| 最終ジャッジ日時 | 2024-09-19 22:00:02 |
| 合計ジャッジ時間 | 10,036 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | RE | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | MLE | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
ソースコード
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
const int MIN_N = 2;
const int MAX_N = 100;
const int MAX_M = 100;
const int MIN_D = 1;
const int MAX_D = 1e8;
const int MIN_c = 1;
const int MAX_c = 1e8;
const int MIN_d = 1;
const int MAX_d = 1e8;
struct UnionFind {
vector<int> d;
int m; // number of connected components
UnionFind(int n = 0) : d(n, -1), m(n) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (d[x] > d[y]) swap(x, y);
d[x] += d[y];
d[y] = x;
--m;
return true;
}
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -d[find(x)]; }
};
signed main(int argc, char* argv[]) {
registerValidation(argc, argv);
int N = inf.readInt(MIN_N, MAX_N, "N");
inf.readSpace();
int M = inf.readInt(N-1, MAX_M, "M");
inf.readSpace();
int D = inf.readInt(MIN_D, MAX_D, "D");
inf.readEoln();
set<pair<int, int>> S;
UnionFind uf(N);
rep(i, M) {
int a = inf.readInt(1, N, "a");
inf.readSpace();
int b = inf.readInt(1, N, "b");
inf.readSpace();
int c = inf.readInt(MIN_c, MAX_c, "c");
inf.readSpace();
int d = inf.readInt(MIN_d, MAX_d, "d");
inf.readEoln();
assert(S.find({a, b}) == S.end());
assert(S.find({b, a}) == S.end());
S.emplace(a, b);
uf.unite(a, b);
}
assert(uf.m == 1);
inf.readEof();
}