QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183150 | #4898. 基础图论练习题 | hos_lyric# | 12 | 65ms | 19684kb | C++14 | 5.7kb | 2023-09-19 06:20:59 | 2024-07-04 02:03:26 |
Judging History
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%