QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721851#5548. Increase the Toll FeesKeeperHihi#TL 496ms12112kbC++202.5kb2024-11-07 17:00:392024-11-07 17:00:39

Judging History

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

  • [2024-11-07 17:00:39]
  • 评测
  • 测评结果:TL
  • 用时:496ms
  • 内存:12112kb
  • [2024-11-07 17:00:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct DSU {
    vector<int> f, siz;
    vector<vector<int>> pos;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
        pos.assign(n + 1, {});
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return 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 (pos[x].size() < pos[y].size()) {
        	swap(pos[x], pos[y]);
        }
        for (auto idx : pos[y]) {
        	pos[x].emplace_back(idx);
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

void solve() {
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> edge;
	vector<int> vis(m);
	vector<int> y;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a > b) swap(a, b);
		edge.emplace_back(c, a, b);
		y.emplace_back(c);
	}
	sort(y.begin(), y.end());
	y.resize(unique(y.begin(), y.end()) - y.begin());
	for (auto &[w, u, v] : edge) {
		w = lower_bound(y.begin(), y.end(), w) - y.begin();
	}
	sort(edge.begin(), edge.end());

	DSU dsu(n);
	for (int i = 0; i < m; i++) {
		auto [w, u, v] = edge[i];
		if (dsu.same(u, v)) {
			continue;
		}
		vis[i] = 1;
		dsu.merge(u, v);
	}

	dsu.init(n);
	i64 ans = 0;
	for (int i = 0; i < m; i++) {
		if (vis[i]) {
			auto [w, u, v] = edge[i];
			ans -= y[w];
		}
	}

	for (int i = 0; i < m; i++) {
		auto [w, u, v] = edge[i];
		u = dsu.find(u);
		v = dsu.find(v);
		if (vis[i]) {
			dsu.pos[u].emplace_back(i);
			continue;
		}
		if (dsu.same(u, v)) continue;
		dsu.merge(u, v);

		vector<int> nex;
		for (auto idx : dsu.pos[u]) {
			auto [a, u, v] = edge[idx];
			if (dsu.same(u, v)) {
				ans += y[w] + 1;
			} else {
				nex.emplace_back(idx);
			}
		}
		swap(dsu.pos[u], nex);
	}
	if (dsu.size(1) != n) {
		cout << "-1\n";
		return;
	}
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t = 1;
	// cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

4 6
1 2 2
1 3 5
1 4 5
2 3 3
2 4 5
3 4 4

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3 4
1 2 3
2 3 4
1 3 5
1 3 10

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

5 10
1 2 14
1 3 14
1 4 9
1 5 15
2 3 8
2 3 10
2 4 13
3 4 8
4 5 10
4 5 15

output:

21

result:

ok single line: '21'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

2 1
1 2 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 379ms
memory: 7076kb

input:

29171 100000
7223 21138 270743473
5598 27967 847631606
12666 26050 847631606
75 15747 270743473
8522 12955 847631606
6069 23750 270743473
18708 22605 847631606
16814 22169 847631606
11550 27119 847631606
562 15959 847631606
9400 11110 270743473
15325 23805 270743473
19169 24404 270743473
6649 12062 ...

output:

16827826868780

result:

ok single line: '16827826868780'

Test #6:

score: 0
Accepted
time: 496ms
memory: 9756kb

input:

47977 200000
10970 47321 440845807
1166 29708 767952745
319 37520 546280762
17581 29425 558321466
22079 26884 344816304
7479 44260 791002634
14685 44163 837529020
1537 10359 330017953
8634 27064 969738917
32950 37192 728271930
34751 42782 63025978
32540 34226 86057211
36786 46050 826927874
30444 436...

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 26ms
memory: 6720kb

input:

28825 57648
9446 22014 286256842
14902 20222 14175
3246 20218 80493268
1783 13768 931622563
11107 24862 918832025
25070 27312 98899079
8535 20222 16037
9184 17491 294248461
8799 17834 456827944
1152 11687 960740527
17849 23045 9706
5774 21436 444202963
5417 23045 3092
20222 20370 11232
16585 20222 1...

output:

28822649262260

result:

ok single line: '28822649262260'

Test #8:

score: 0
Accepted
time: 224ms
memory: 9504kb

input:

22253 200000
46 10310 674985053
2403 19582 788128238
5203 7897 985236456
2709 9034 824557880
14337 20524 230824854
19901 22177 99959362
5067 8568 570267383
13707 21474 610729058
7494 7860 109319713
14473 16182 794578653
21 17055 852110939
19320 21640 844993191
2443 21673 170358534
5941 9705 16465049...

output:

3270266304988

result:

ok single line: '3270266304988'

Test #9:

score: 0
Accepted
time: 265ms
memory: 6488kb

input:

24396 100000
2931 7546 930776437
29 7070 602517959
9822 15137 930776437
8704 9393 930776437
9948 19773 930776437
14323 16751 930776437
6249 19840 930776437
11692 16925 930776437
8806 13126 930776437
13600 23061 930776437
738 21253 930776437
8142 16750 930776437
3498 23353 930776437
8769 23254 930776...

output:

8007865595205

result:

ok single line: '8007865595205'

Test #10:

score: 0
Accepted
time: 138ms
memory: 8696kb

input:

20147 200000
8151 8515 682552832
9950 17609 401979729
2320 16777 623704514
12160 18944 584466480
14548 18229 573286673
1849 2446 288691450
12937 19825 748755808
15533 16212 931321301
960 4132 465223013
2102 19779 143370818
8177 10702 194163825
6217 8093 190716214
7912 17254 788498808
15915 16392 396...

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0
Accepted
time: 45ms
memory: 8148kb

input:

44967 89932
4611 22256 288245643
13129 41735 40940
26585 28192 22377
13129 18756 35813
244 24542 392777697
3170 13129 10602
5106 13129 3108
12697 43383 520646529
8665 38358 657175335
8174 22928 146486000
13129 42450 29798
20450 31848 601056112
26585 35000 37292
166 29044 536220871
1775 13686 9371272...

output:

44963069583727

result:

ok single line: '44963069583727'

Test #12:

score: 0
Accepted
time: 128ms
memory: 11656kb

input:

100000 150000
61412 88694 183559127
63436 73299 894859967
26602 46436 786301216
1338 12025 782274652
23565 55101 978497921
8423 12177 987621555
26437 59897 512205670
25428 90394 99802072
34439 96521 36264639
3514 47608 31833243
27862 59455 161754672
13730 65287 750535148
8174 74169 84643097
77653 80...

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 80ms
memory: 10240kb

input:

100000 199998
1740 95147 410564287
14057 30242 975301572
44406 68640 99197243
25206 33319 147706560
36836 82726 532371198
20169 20381 157910525
27802 94319 355487781
74596 90242 153032027
27347 85192 206476264
10053 84568 938334959
70186 94117 154520026
56539 64797 284929069
3156 51928 346065715
652...

output:

199998

result:

ok single line: '199998'

Test #14:

score: 0
Accepted
time: 71ms
memory: 12112kb

input:

100000 199998
21029 24465 1
20281 70033 1000000000
80966 83405 1
182 91462 1
11471 80105 1
44728 64299 1000000000
28235 37983 1000000000
29478 73083 1000000000
39551 66918 1
44691 83002 1
6717 74353 1
8546 39620 1000000000
25795 72680 1000000000
18738 53936 1000000000
54601 98620 1000000000
30462 76...

output:

99999000000000

result:

ok single line: '99999000000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

2 2
1 2 1
1 2 1000000000

output:

1000000000

result:

ok single line: '1000000000'

Test #16:

score: 0
Accepted
time: 98ms
memory: 11724kb

input:

100000 199998
6428 66622 140276399
45806 66068 24480468
27996 75977 238456054
22694 40930 246531711
7996 65658 817165171
8354 88303 818881672
5417 28577 743249294
45892 78967 941072773
67230 86764 793683381
25148 94217 889440410
24364 76989 72031957
32897 70536 252745043
42569 98426 598450133
53879 ...

output:

33452348231419

result:

ok single line: '33452348231419'

Test #17:

score: 0
Accepted
time: 77ms
memory: 8292kb

input:

492 200000
243 351 729773927
25 119 546768431
60 137 442503509
1 208 521544290
116 241 616544481
144 327 197607774
83 205 486182087
52 450 429246768
68 476 370698523
102 439 997049507
289 317 781589140
271 383 499974515
99 436 807262087
177 364 673711522
432 492 968138053
203 319 653023170
164 228 3...

output:

-1

result:

ok single line: '-1'

Test #18:

score: -100
Time Limit Exceeded

input:

100000 200000
84171 84739 505815970
17361 59167 948077627
25317 90899 272978612
33900 84218 346991489
29646 94826 981152764
11714 36825 926502871
73525 80993 659061656
10733 16853 626788053
21943 45826 430265524
11089 20657 155519370
54702 94924 284275764
37517 67203 953992098
4102 74402 82177808
17...

output:


result: