QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#588102 | #415. 最小生成树 | shiqiaqiaya | 100 ✓ | 152ms | 22444kb | C++17 | 3.9kb | 2024-09-25 01:19:35 | 2024-09-25 01:19:36 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using ll = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K, class V = null_type, class C = less<>> using rb_tree = tree<K, V, C, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const ll mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);
template <ll mod = mod> ll binpow(ll a, ll b, ll res = 1) {
for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
if (b & 1) (res *= a) %= mod;
}
return res;
}
vector<signed> inv, fact, invfa;
auto INIT_FACT = ([](int n) {
inv = fact = invfa = vector<signed>(n + 1, 1);
for (int i = 2; i <= n; i++) {
fact[i] = (ll)fact[i - 1] * i % mod, invfa[i] = (ll)invfa[i - 1] * (inv[i] = (mod - mod / i) * inv[mod % i] % mod);
}
} (0), true);
ll C(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[m] % mod * invfa[n - m] % mod; }
ll P(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[n - m] % mod; }
ll LC(ll n, ll m) { return !m ? 1 : C(n % mod, m % mod) * LC(n / mod, m / mod) % mod; }
// vector<int> dfn, dcc, is_bridge;
// vector dc(0, vector<int>());
// [&](int n, int m, int tot_dfn = 0) {
// vector<int> low(n + 1); // 邻接表要记录编号
// dfn = dcc = vector<int>(n + 1), is_bridge = vector<int>(m + 1);
// for (int root = 1; root <= n; root++) {
// stack<int> s;
// auto Tarjan = [&](auto && Tarjan, int u, int from_edge) -> void {
// s.push(u); dfn[u] = low[u] = ++tot_dfn;
// for (auto & i : adj[u]) {
// int v = e[i][0] ^ e[i][1] ^ u;
// if (!dfn[v]) {
// Tarjan(Tarjan, v, i);
// low[u] = min(low[u], low[v]);
// if (low[v] > dfn[u]) {
// is_bridge[i] = true;
// }
// } else if (i != from_edge) { //用from_edge而不用father是因为可能重边
// low[u] = min(low[u], dfn[v]);
// }
// }
// if (dfn[u] == low[u]) {
// vector<int> tmp;
// while (!tmp.size() || tmp.back() != u) {
// int v = s.top(); s.pop();
// dcc[v] = dc.size(), tmp.push_back(v);
// }
// dc.push_back(tmp);
// }
// };
// if (!dfn[root]) {
// Tarjan(Tarjan, root, -1);
// }
// }
// } ();
// struct Tarjan_UnDir : {
// };
struct DSU : vector<signed> {
DSU(int n) : vector(n) { iota(begin(), end(), 0); }
int find(int u) { return at(u) == u ? u : at(u) = find(at(u)); }
int merge(int u, int v) { return find(u) == find(v) ? -1 : at(find(u)) = find(v); }
};
struct Kruskal : vector<array<int, 3>> {
DSU dsu;
int sum;
vector res;
Kruskal(int n, int m) : vector(m), dsu(n), sum(0) {}
template <class C = less<>> void get(C && cmp = C()) {
sort(begin(), end(), cmp);
for (auto & [w, u, v] : *this) {
if (dsu.merge(u, v) != -1) sum += w, res.emplace_back(array{w, u, v});
}
}
};
void QAQ() {
int n, m;
cin >> n >> m;
Kruskal e(n + 1, m);
for (int i = 0; i < m; i++) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
}
e.get();
cout << e.sum << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
// cin >> t;
for (cout << fixed << setprecision(12); t--; QAQ());
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3628kb
input:
1 0
output:
0
result:
ok answer is '0'
Test #2:
score: 10
Accepted
time: 103ms
memory: 15136kb
input:
1 500000 1 1 436085873 1 1 289134331 1 1 95168426 1 1 809912668 1 1 912905316 1 1 51427205 1 1 808052925 1 1 168547991 1 1 469573116 1 1 7523372 1 1 700424384 1 1 329491017 1 1 886380039 1 1 92596215 1 1 870407506 1 1 420928567 1 1 29439913 1 1 851970613 1 1 595343843 1 1 150074451 1 1 981248098 1 1...
output:
0
result:
ok answer is '0'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3728kb
input:
1049 1095 37 1027 185663189 439 923 842401821 92 68 172561838 108 320 929023969 537 284 451497914 161 836 18296000 101 14 582350247 82 947 633276668 555 731 321285985 282 946 133823187 549 982 59411620 19 151 982845654 961 22 185979994 201 958 42654715 178 446 121754463 100 386 87537747 492 486 2228...
output:
459312924580
result:
ok answer is '459312924580'
Test #4:
score: 10
Accepted
time: 129ms
memory: 15244kb
input:
1677 500000 1010 1055 334171722 32 548 496908773 1662 273 215127528 1596 969 799111789 993 895 816193284 335 56 975688725 1537 1674 694838017 512 1006 84989138 487 1094 77423013 1131 522 260247889 32 1581 652804125 1472 1609 861174323 1083 230 236457705 1009 593 692730522 709 284 647880265 936 1598 ...
output:
3426870407
result:
ok answer is '3426870407'
Test #5:
score: 10
Accepted
time: 125ms
memory: 15260kb
input:
4782 500000 401 2704 143282494 408 742 221495274 2487 2740 328112333 1471 3347 678117943 2369 3844 94084087 4137 629 771103 1506 2976 377332399 3856 3529 15354521 977 1747 267860558 2561 1837 234002816 1947 1191 447985398 2575 3486 210906740 321 1319 879712756 3660 3019 926744290 4492 528 110850246 ...
output:
20391912348
result:
ok answer is '20391912348'
Test #6:
score: 10
Accepted
time: 63ms
memory: 12712kb
input:
100000 250000 11249 63248 716981925 77587 45081 715237577 40869 43888 384028427 68447 21259 718879057 15416 4835 542698454 86984 39250 200243926 38485 9822 321829618 68650 80338 208779180 93995 71720 970100731 62306 65602 758670337 12962 93202 405549936 11239 70788 481995017 65169 11656 137255256 93...
output:
19768912676568
result:
ok answer is '19768912676568'
Test #7:
score: 10
Accepted
time: 71ms
memory: 13276kb
input:
100000 250000 58087 98694 276928916 81020 20563 474360924 54330 72482 965233532 69316 62625 693679792 68391 25019 626212979 66635 9065 208396713 18722 31967 29636156 18804 17430 126344131 52091 61058 813889563 22524 92717 616323226 91592 59352 7003125 39568 15009 745751969 59457 33731 34864625 3185 ...
output:
19671766809300
result:
ok answer is '19671766809300'
Test #8:
score: 10
Accepted
time: 47ms
memory: 16704kb
input:
200000 199999 65210 94695 20344717 27677 60426 947830254 44160 166001 68537440 144553 10242 174779136 72796 113802 266364597 1858 24797 628448494 194099 76945 666582594 133683 17237 128244232 152149 91422 110103130 150169 10041 739399998 136455 75250 7894691 81174 102926 26871471 27780 63438 7883747...
output:
94124014988825
result:
ok answer is '94124014988825'
Test #9:
score: 10
Accepted
time: 131ms
memory: 22444kb
input:
200000 500000 46671 50310 339946279 111950 44341 976219244 183028 30375 283623377 119684 483 278812425 123223 173434 86847632 53396 67926 343986583 195715 85791 872435965 51759 67385 324694963 132645 146330 74109089 142363 58800 508205119 151247 105471 160455427 97528 133772 68416120 33125 33151 102...
output:
39818560453301
result:
ok answer is '39818560453301'
Test #10:
score: 10
Accepted
time: 152ms
memory: 22400kb
input:
200000 500000 45588 17449 500297001 167443 90625 840063438 184162 31916 123322602 75130 105595 80124915 4990 23835 842648585 198193 138933 377398791 61179 68315 899014505 170138 8312 214877618 130847 183955 648135341 186493 178082 135732043 34104 128022 298311436 180739 90096 241294500 90919 4640 35...
output:
39679281240808
result:
ok answer is '39679281240808'