QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721447#5548. Increase the Toll FeesKeeperHihi#TL 32ms12212kbC++203.0kb2024-11-07 16:07:552024-11-07 16:07:55

Judging History

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

  • [2024-11-07 16:07:55]
  • 评测
  • 测评结果:TL
  • 用时:32ms
  • 内存:12212kb
  • [2024-11-07 16:07:55]
  • 提交

answer

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

struct DSU {
    vector<int> f, siz;
    
    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);
    }
    
    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;
        }
        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());

	// for (auto [w, u, v] : edge) {
	// 	cout << u << ' ' << v << ' ' << w << endl;
	// }

	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);
	}
	// for (int i = 0; i < m; i++) {
	// 	cout << vis[i] << " \n"[i + 1 == m];
	// }

	dsu.init(n);
	vector<vector<int>> tong(m + 1);
	for (int i = 0; i < m; i++) {
		auto [w, u, v] = edge[i];
		tong[w].emplace_back(i);
	}
	int ans = 0;
	// for (int i = 0; i < m; i++) {
	// 	cout << y[i] << " \n"[i + 1 == m];
	// }
	for (int i = 0; i < m; i++) {
		// cout << "i = " << i << endl;
		// for (int j = 0; j < m; j++) {
		// 	cout << "j = " << j << " : ";
		// 	for (auto t : tong[j]) {
		// 		cout << t << ' ';
		// 	} 
		// 	cout << endl;
		// }
		vector<int> cur;
		for (auto idx : tong[i]) {
			auto [w, u, v] = edge[idx];
			if (vis[idx]) {
				cur.emplace_back(idx);
			} else {
				if (!dsu.same(u, v)) {
					dsu.merge(u, v);
				} 
			}
		}
		vector<int> nex;
		// for (auto t : cur) cout << t << ' '; cout << endl;
		for (auto idx : cur) {
			auto [w, u, v] = edge[idx];
			if (dsu.same(u, v)) {
				// cout << "hello : " << y[i] << ' ' << w << endl;
				ans += y[i] + 1 - y[w];
			} else {
				nex.emplace_back(idx);
			}
		}
		if (nex.size() > tong[i + 1].size()) {
			swap(nex, tong[i + 1]);
		}
		for (auto t : nex) {
			tong[i + 1].emplace_back(t);
		}
		// cout << "ans = " << ans << endl;
	}
	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: 3612kb

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: 3616kb

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: 3556kb

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: 3616kb

input:

2 1
1 2 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 32ms
memory: 12212kb

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: -100
Time Limit Exceeded

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:


result: