QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#916420#415. 最小生成树Floze3#100 ✓57ms12684kbC++207.5kb2025-02-26 20:45:572025-02-26 20:45:58

Judging History

This is the latest submission verdict.

  • [2025-02-26 20:45:58]
  • Judged
  • Verdict: 100
  • Time: 57ms
  • Memory: 12684kb
  • [2025-02-26 20:45:57]
  • Submitted

answer

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#ifdef CPH
#include "/home/floze3/OI/debug.hpp"
#else 
#include "/home/floze3/OI/debug_colored.hpp"
#endif
#else
#define debug(...) 42
#define debugArr(...) 42
#define look_time 42
#define look_memory 42
#endif
#define mp(x, y) std::make_pair(x, y)
#define mt std::make_tuple
#define eb emplace_back
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define file(name)                 \
  freopen(name ".in", "r", stdin); \
  freopen(name ".out", "w", stdout);
#define fs(x) std::fixed << std::setprecision(x)
#define il inline
#define Avada_Kedavra return 0
#define _IOS                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(nullptr), std::cout.tie(nullptr)
#define RANDOM_SEED std::chrono::steady_clock::now().time_since_epoch().count()
#define multitask    \
  int _; rd >> _; \
  while (_--)
using std::cerr;

namespace TYPEDEF {

using i32 = int32_t;
using i64 = long long;
using u64 = unsigned long long;
using u32 = uint32_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = std::pair<i32, i32>;
using pi64 = std::pair<i64, i64>;
using vi = std::vector<i32>;
using vu = std::vector<u32>;
using vi64 = std::vector<i64>;
using vu64 = std::vector<u64>;
using vpii = std::vector<pii>;
using vpi64 = std::vector<pi64>;
using si = std::stack<i32>;
using si64 = std::stack<i64>;
using su64 = std::stack<u64>;
using spii = std::stack<pii>;
using spi64 = std::stack<pi64>;
using qi = std::queue<i32>;
using qi64 = std::queue<i64>;
using qu64 = std::queue<u64>;
using qpii = std::queue<pii>;
using qpi64 = std::queue<pi64>;
using siset = std::set<i32>;
using si64set = std::set<i64>;
using su64set = std::set<u64>;
using spiiset = std::set<pii>;
using spi64set = std::set<pi64>;
using str = std::string;
using vstr = std::vector<str>;
using f64 = long double;
template <typename T> using vc = std::vector<T>;
template <typename FI, typename SE> using pr = std::pair<FI, SE>;

} // namespaec TYPEDEF

using namespace TYPEDEF;

struct Scanner {
  FILE* stream;
  Scanner(FILE* s): stream(s) {}
  char buf[1 << 20], *l = buf, *r = buf;
  bool flush() { l = buf; r = l + fread(buf, 1, 1 << 20, stream); return l == r; }
  void get(char &c) {
#ifndef ONLINE_JUDGE
    c = getchar();
#else
    c = l == r && flush() ? ' ' : *l++;
#endif
  }

  friend Scanner &operator>>(Scanner &in, char &c) { return in.get(c), in; }

  friend Scanner &operator>>(Scanner &in, char* s) {
    for (in.get(s[0]); isspace(s[0]); in.get(s[0]));
    for (i32 i = 0; !isspace(s[i]) || (s[i] = '\0'); i++) in.get(s[i + 1]);
    return in;
  }

  friend Scanner &operator>>(Scanner &in, str &s) {
    char c;
    for (in.get(c); isspace(c); in.get(c));
    for (s = ""; !isspace(c); in.get(c)) s += c;
    return in;
  }

  friend Scanner &operator>>(Scanner &in, i128 &x) {
    char c, f = '+';
    for (in.get(c); !isdigit(c); in.get(c))
      if (c == '-') f = c;
    for (x = 0; isdigit(c); in.get(c)) x = (x << 1) + (x << 3) + c - '0';
    if (f == '-') x = -x;
    return in;
  }

  template <class T> requires std::is_integral_v<T>
  friend Scanner &operator>>(Scanner &in, T &x) {
    char c, f = '+';
    for (in.get(c); !isdigit(c); in.get(c))
      if constexpr (std::is_signed_v<T>) f = c;
    for (x = 0; isdigit(c); in.get(c)) x = x * 10 + c - '0';
    if constexpr (std::is_signed_v<T>) x = f == '-' ? -x : x;
    return in;
  }

  template <class T> requires std::is_floating_point_v<T>
  friend Scanner &operator>>(Scanner &in, T &x) {
    std::string s; in >> s; x = std::stod(s);
    return in;
  }
};

struct Printer {
  FILE* stream;
  Printer(FILE* s): stream(s) {}
  char buf[1 << 20], *l = buf, *r = buf + (1 << 20) - 1;
  int format = 0, precision = 15;
  ~Printer() { flush(); }

  void flush() { fwrite(buf, 1, l - buf, stream); l = buf; }
  void put(const char &c) {
#ifndef ONLINE_JUDGE
    putchar(c);
#else
    *l++ = c;
    if (l == r) flush();
#endif
  }

  friend Printer &operator<<(Printer &out, const char &c) {
    return out.put(c), out;
  }

  friend Printer &operator<<(Printer &out, const char* s) {
    for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
    return out;
  }

  friend Printer &operator<<(Printer &out, char* s) {
    for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
    return out;
  }

  friend Printer &operator<<(Printer &out, const str &s) {
    for (int i = 0, n = s.size(); i < n; i++) out.put(s[i]);
    return out;
  }

  friend Printer &operator<<(Printer &out, i128 x) {
    static short s[40], top = 0;
    if (x < 0) out.put('-'), x = -x;
    do s[++top] = x % 10, x /= 10; while (x);
    while (top) out.put(s[top--] + '0');
    return out;
  }

  template <typename T> requires std::is_integral_v<T>
  friend Printer& operator <<(Printer &out, T x) {
    static short s[40];
    static i32 i = 0;
    if (x == 0) { out.put('0'); return out; }
    if constexpr (std::is_signed_v<T>) x = x < 0 ? out.put('-'), -x : x;
    while (x > 0) s[++i] = x % 10 + '0', x /= 10;
    while (i > 0) out.put(s[i--]);
    return out;
  }

  template <typename T> requires std::is_floating_point_v<T>
  friend Printer& operator <<(Printer &out, T x) {
    std::ostringstream oss;
    oss << std::fixed << std::setprecision(out.precision) << x;
    return out << oss.str();
  }
};

Scanner rd(stdin);
Printer wt(stdout);

/*===============================ALGOS===============================*/

namespace basic_algorithm {
template <typename T> il T abs(T a) { return a >= 0 ? a : -a; }
template <typename T> il void chmin(T &a, T b) { if (a > b) a = b; }
template <typename T> il void chmax(T &a, T b) { if (a < b) a = b; }
template <typename T> il T lowbit(T x) { return (x & (-x)); }
il i32 pct(i32 x) { return __builtin_popcount(x); }
il i32 pct(u32 x) { return __builtin_popcount(x); }
il i32 pct(i64 x) { return __builtin_popcountll(x); }
il i32 pct(u64 x) { return __builtin_popcountll(x); }
}  // namespace basic_algorithm

using namespace basic_algorithm;

/*================================END================================*/

constexpr i32 N = 2e5 + 5;
constexpr i32 M = 5e5 + 5;
constexpr i32 mod = 1e9 + 7;
constexpr i32 inf = 0x3f3f3f3f;
constexpr i64 inf64 = 0x3f3f3f3f3f3f3f3fll;
// constexpr f64 pi = std::numbers::pi_v<f64>;

// std::mt19937 rng(RANDOM_SEED);

bool mst;

i32 n, m;
i64 ans;

struct Edge {
  i32 u, v, w;

  bool operator < (const Edge &rhs) const {
    return w < rhs.w;
  }
} e[M];

struct DSU {
  vi fa, siz;
  
  DSU() {}
  DSU(int n) { init(n); }
  
  void init(int n) {
    fa.resize(n + 1), siz.resize(n + 1);
    for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
    return ;
  }
  
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  
  bool same(int x, int y) { return find(x) == find(y); }
  
  bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) std::swap(x, y);
    fa[y] = x, siz[x] += siz[y];
    return true;
  }
  
  il int size(int x) { return siz[find(x)]; }
};

bool med;

signed main() {
  rd >> n >> m;
  for (i32 i = 1; i <= m; ++i)
    rd >> e[i].u >> e[i].v >> e[i].w;
  DSU d(n);
  std::sort(e + 1, e + 1 + m);
  for (i32 i = 1; i <= m; ++i) {
    if (!d.same(e[i].u, e[i].v)) {
      d.merge(e[i].u, e[i].v);
      ans += e[i].w;
    }
  }
  wt << ans;
  Avada_Kedavra;
}

/*
all the things you do
the words you say
it all comes back to you
*/

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 5708kb

input:

1 0

output:

0

result:

ok answer is '0'

Test #2:

score: 10
Accepted
time: 41ms
memory: 11568kb

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: 0ms
memory: 5484kb

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: 45ms
memory: 11344kb

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: 41ms
memory: 11224kb

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: 25ms
memory: 9716kb

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: 23ms
memory: 9896kb

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: 24ms
memory: 11764kb

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: 57ms
memory: 12684kb

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: 52ms
memory: 12552kb

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'