QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287428 | #5048. All Pair Maximum Flow | Smallbasic | WA | 7ms | 30452kb | C++14 | 2.0kb | 2023-12-20 15:36:10 | 2023-12-20 15:36:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5, mod = 998244353;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
typedef long long ll;
int u[N], v[N], n, m, f[N], siz[N];
ll w[N];
bool vis[N];
set<pair<ll, int> > conv;
set<pair<int, int> > e[N];
inline void del(int i) {
conv.erase(make_pair(w[i], i));
e[u[i]].erase(make_pair(v[i], i));
e[v[i]].erase(make_pair(u[i], i));
}
inline int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
n = read(); m = read();
for (int i = 1; i <= m; ++i) {
u[i] = read(); v[i] = read(); w[i] = read();
if (u[i] > v[i]) swap(u[i], v[i]);
if (v[i] == u[i] + 1 || (v[i] == n && u[i] == 1)) conv.insert(make_pair(w[i], i));
e[u[i]].insert(make_pair(v[i], i));
e[v[i]].insert(make_pair(u[i], i));
} int T = m - (n - 1);
while (T--) {
int x = conv.begin() -> second;
del(x); vis[x] = 1;
int now = u[x], lst = v[x];
while (now != v[x]) {
set<pair<int, int> > :: iterator it = e[now].upper_bound(make_pair(lst, 0x3f3f3f3f));
if (it == e[now].end()) it = e[now].begin();
int i = it -> second;
if (conv.find(make_pair(w[i], i)) == conv.end()) {
w[i] += w[x];
conv.insert(make_pair(w[i], i));
if (u[i] != now) swap(u[i], v[i]);
} else {
del(i);
w[i] += w[x];
} lst = now; now = it -> first;
}
} for (int i = 1; i <= n; ++i) f[i] = i, siz[i] = 1;
conv.clear(); int res = 0;
for (int i = 1; i <= m; ++i)
if (!vis[i]) conv.insert(make_pair(-w[i], i));
for (pair<ll, int> i : conv) {
int x = u[i.second], y = v[i.second];
x = find(x); y = find(y);
res += 1ll * (w[i.second] % mod) * (1ll * siz[x] * siz[y] % mod) % mod;
if (res >= mod) res -= mod;
f[x] = y; siz[y] += siz[x];
} printf("%d\n", res); return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 30452kb
input:
6 8 1 2 1 2 3 10 3 4 100 4 5 1000 5 6 10000 6 1 100000 1 4 1000000 1 5 10000000
output:
12343461
result:
ok 1 number(s): "12343461"
Test #2:
score: 0
Accepted
time: 7ms
memory: 29436kb
input:
20 30 5 7 9066926 13 15 636587393 1 12 234024833 7 11 863853881 7 9 961926707 12 20 525748907 7 10 217196987 15 20 715248370 17 19 577652480 16 19 78750484 1 2 216519168 2 3 26083428 3 4 381598120 4 5 78513523 5 6 106643887 6 7 20069507 7 8 467260856 8 9 383736316 9 10 400897545 10 11 404258163 11 1...
output:
858325335
result:
ok 1 number(s): "858325335"
Test #3:
score: 0
Accepted
time: 0ms
memory: 29976kb
input:
20 26 13 17 325133268 9 18 216183439 2 7 16535651 4 6 390851818 12 17 381307448 9 17 980041383 1 2 141256756 2 3 688869622 3 4 579655258 4 5 570436112 5 6 293656896 6 7 988638554 7 8 887938206 8 9 413776002 9 10 983955283 10 11 198400568 11 12 434019230 12 13 960512608 13 14 942127959 14 15 75671628...
output:
286660015
result:
ok 1 number(s): "286660015"
Test #4:
score: 0
Accepted
time: 3ms
memory: 29272kb
input:
20 30 12 14 28222897 2 4 425326589 8 19 985232890 9 15 330291477 9 11 199514528 7 20 148246184 9 14 771529315 1 7 74025894 1 4 121592328 16 19 533025399 1 2 656923794 2 3 251967493 3 4 905936081 4 5 218526186 5 6 298821633 6 7 141173509 7 8 823436709 8 9 266422723 9 10 570882032 10 11 434809298 11 1...
output:
31481143
result:
ok 1 number(s): "31481143"
Test #5:
score: -100
Wrong Answer
time: 7ms
memory: 29912kb
input:
200 379 184 191 236609500 178 180 710537395 12 34 803762294 164 166 77794954 75 91 229922975 4 199 403835359 98 109 275493753 74 91 8512493 99 105 430613927 42 45 20773932 174 184 872427370 157 160 374930702 130 138 377241825 113 116 813473613 171 173 951985709 76 90 789580090 174 191 588309194 54 5...
output:
441815755
result:
wrong answer 1st numbers differ - expected: '920791837', found: '441815755'