QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183150#4898. 基础图论练习题hos_lyric#12 65ms19684kbC++145.7kb2023-09-19 06:20:592024-07-04 02:03:26

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:03:26]
  • 评测
  • 测评结果:12
  • 用时:65ms
  • 内存:19684kb
  • [2023-09-19 06:20:59]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;

int root(vector<int> &uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf, uf[u]));
}
bool connect(vector<int> &uf, int u, int v) {
  u = root(uf, u);
  v = root(uf, v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


Int N;
int A, B;
vector<Int> D;
vector<int> X;
vector<Int> U, V;
vector<int> W;

vector<pair<int, int>> es;


namespace brute {
constexpr int F = 19;
vector<int> ufs[F];

// (u, v), (u + 1, v + 1), ..., (u + 2^f-1, v + 2^f-1)
int rec(int f, int u, int v) {
  int ret = 0;
  if (connect(ufs[f], u, v)) {
    if (f) {
      ret += rec(f - 1, u, v);
      ret += rec(f - 1, u + (1 << (f-1)), v + (1 << (f-1)));
    } else {
      ret += 1;
    }
  }
  return ret;
}

Mint run() {
  for (int f = 0; f < F; ++f) {
    ufs[f].assign(N, -1);
  }
  Mint ans = 0;
  for (const auto &e : es) {
    int num = 0;
    if (e.second < A) {
      const int a = e.second;
      const int f = 31 - __builtin_clz(N - D[a]);
      num += rec(f, 0, D[a]);
      num += rec(f, N - D[a] - (1 << f), N - (1 << f));
    } else {
      const int b = e.second - A;
      num += rec(0, U[b], V[b]);
    }
// cerr<<e<<": "<<num<<endl;
    ans += Mint(e.first) * num;
  }
  return ans;
}
}  // brute


int main() {
  for (; ~scanf("%lld%d%d", &N, &A, &B); ) {
    D.resize(A);
    X.resize(A);
    for (int a = 0; a < A; ++a) {
      scanf("%lld%d", &D[a], &X[a]);
    }
    U.resize(B);
    V.resize(B);
    W.resize(B);
    for (int b = 0; b < B; ++b) {
      scanf("%lld%lld%d", &U[b], &V[b], &W[b]);
    }
cerr<<"N = "<<N<<", A = "<<A<<", B = "<<B<<endl;
    
    es.resize(A + B);
    for (int a = 0; a < A; ++a) {
      es[a] = make_pair(X[a], a);
    }
    for (int b = 0; b < B; ++b) {
      es[A + b] = make_pair(W[b], A + b);
    }
    sort(es.begin(), es.end());
    
    Mint ans = 0;
    {
      ans = brute::run();
    }
    printf("%u\n", ans.x);
  }
  return 0;
}

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 15ms
memory: 16832kb

input:

161199 9 46510
147335 540442844
159493 801351455
149342 821625305
128476 843250712
95524 275754315
139315 106523502
93575 680460786
155498 328812257
146020 410466645
79992 141967 50596784
152210 68644 268349216
72549 96959 42994091
93869 27394 945120577
2909 81886 270684270
12735 35026 871917997
974...

output:

359714743

result:

ok 1 number(s): "359714743"

Test #2:

score: 0
Accepted
time: 21ms
memory: 17256kb

input:

168549 9 49402
160577 34610415
114623 670751010
74448 676966248
53782 845469137
130729 375561046
31610 261496571
134601 154875802
136129 905308676
166248 499420220
69637 72676 875637640
160442 125460 1269794
146261 61770 714794725
137610 1291 490170432
162092 81850 488118013
106400 48193 276190368
4...

output:

520439176

result:

ok 1 number(s): "520439176"

Test #3:

score: 0
Accepted
time: 21ms
memory: 14136kb

input:

127164 9 45109
56483 490066497
70966 229077054
87305 993081887
72423 442762798
80262 200507011
101712 162752728
67532 590730535
44956 565466274
124237 429166816
13030 8906 742024040
97259 101468 187678659
13401 4301 143856524
125750 80473 258719294
106155 10339 592121345
120034 92354 50915550
112430...

output:

211463174

result:

ok 1 number(s): "211463174"

Test #4:

score: 0
Accepted
time: 18ms
memory: 16412kb

input:

158784 9 48415
138305 177767002
147417 50196642
85527 776201932
144377 990389932
118355 310906417
145220 218744495
145002 132736644
51947 834751363
139733 839880491
158443 157692 159261414
111518 14927 747973081
37498 66196 69874791
11597 115114 22394413
16704 133459 109302190
112143 46551 813021872...

output:

151875883

result:

ok 1 number(s): "151875883"

Test #5:

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

input:

111371 0 45933
13298 59545 852258097
94111 54245 459369673
40744 23311 644404848
37039 92443 220984611
17374 43165 421794343
57652 57965 470479953
62977 14481 563172671
102144 3471 36594913
46628 43278 11508424
55965 80136 777230453
56962 35374 349098036
34825 27995 339605509
43021 17657 780921827
5...

output:

92500087

result:

ok 1 number(s): "92500087"

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 8
Accepted
time: 62ms
memory: 19684kb

input:

191116 49595 45279
87483 815631830
153579 433065789
167569 346797140
98560 154881536
170720 13622837
133236 561208103
155537 421316363
140536 514298139
6005 986290017
154400 85233907
166826 351094521
174419 304435906
173900 61174962
112778 693574534
104503 745038995
134920 31228457
117606 662581798
...

output:

938591083

result:

ok 1 number(s): "938591083"

Test #7:

score: 0
Accepted
time: 51ms
memory: 17448kb

input:

158784 46472 48415
117545 640905746
155053 431989480
155561 63255800
142377 310683680
127120 588058774
150004 169474069
127002 588668628
150906 152304212
108743 687077799
41914 919104130
85429 816335084
132059 559711015
9237 981038801
108448 689051256
152572 446125546
151056 149667391
3602 992249821...

output:

719582900

result:

ok 1 number(s): "719582900"

Test #8:

score: 0
Accepted
time: 62ms
memory: 17976kb

input:

168163 49816 47597
129571 532707978
89007 791596146
120950 589183161
116493 617468410
89768 786647320
94035 758413684
137865 480953267
136999 487494650
134286 503698037
115468 623920627
128035 542927955
91335 776005194
150127 398148336
2766 992431297
143028 109308374
98376 730561618
135270 13761588
...

output:

934807905

result:

ok 1 number(s): "934807905"

Test #9:

score: 0
Accepted
time: 47ms
memory: 14724kb

input:

121718 46964 48021
43354 819111261
10530 955367869
80777 501381455
69544 639333275
114691 89113603
45387 810937142
31928 865064071
89801 391744587
94263 339137420
119935 23921502
56223 766531932
108313 167240585
106757 185911175
30245 872961430
71691 612640613
102314 242401520
101122 257170039
61627...

output:

135228392

result:

ok 1 number(s): "135228392"

Test #10:

score: 0
Accepted
time: 65ms
memory: 19588kb

input:

188134 49787 48968
187895 50171716
119433 814368117
139552 750931626
132931 458299971
142653 741277533
177407 244563903
130505 469034750
145157 399488414
173707 262070086
168863 158870562
172377 35902964
140369 421860855
29507 967813282
165485 301042299
143784 737822317
162077 173448746
108264 85153...

output:

100771003

result:

ok 1 number(s): "100771003"

Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

569435269457904707 2 0
490445920091092693 772271583
144842828305643603 609043885

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Runtime Error

Test #31:

score: 0
Runtime Error

input:

755526150476311190 942 0
492334667739348527 1
755523898623296976 1
532486636690994793 1
755526150476030559 1
755526150476249097 1
502164090270592200 1
657422656495814703 1
487200614853438190 1
311037325561173142 1
755526150475651155 1
125287404340238660 1
755524914808674090 1
755526150476177007 1
75...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #5:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%