QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287428#5048. All Pair Maximum FlowSmallbasicWA 7ms30452kbC++142.0kb2023-12-20 15:36:102023-12-20 15:36:10

Judging History

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

  • [2023-12-20 15:36:10]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:30452kb
  • [2023-12-20 15:36:10]
  • 提交

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'