QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721095#5548. Increase the Toll Feeswjt#RE 22ms16532kbC++142.6kb2024-11-07 15:12:462024-11-07 15:12:47

Judging History

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

  • [2024-11-07 15:12:47]
  • 评测
  • 测评结果:RE
  • 用时:22ms
  • 内存:16532kb
  • [2024-11-07 15:12:46]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100005
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int n, m, fa[N], cnt;
struct edge {
	int u, v, w;
	bool tag;
	bool operator < (const edge& t) const { return w < t.w; };
}e[N];

int find(int u) {
	return fa[u] == u ? u : fa[u] = find(fa[u]);
}
vector <edge> pre;
void clear() {
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	cnt = 0;
}

struct node {
	int v, w;
};
vector <node> son[N];
int f[N][20], Max[N][20];


int dep[N], val[N];

void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; (1 << i) <= dep[u]; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i].v, w = son[u][i].w;
		if (v == fa) continue;
		val[v] = w;
		dfs(v, u);
	}
}

void fun(int u, int fa) {
	Max[u][0] = val[u];
	for (int i = 1; i <= 19; i++) {
		Max[u][i] = max(Max[ f[u][i - 1] ][i - 1], Max[u][i - 1]);
	}
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i].v;
		if (v != fa) fun(v, u);
	}
}
int get(int s, int t) {
	int res = -INF;
	if (dep[s] < dep[t]) swap(s, t);
	for (int i = 19; i >= 0; i--) {
		if (dep[s] - (1 << i) >= dep[t]) {
			res = max(res, Max[s][i]);
			s = f[s][i];
		}
	}
	if (s == t) return res;
	for (int i = 19; i >= 0; i--) {
		if (f[s][i] != f[t][i]) {
			res = max(res, max(Max[s][i], Max[t][i]) );
			s = f[s][i];
			t = f[t][i];
		}
	}
	return max(res, max(Max[s][0],Max[t][0]));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
		e[i].tag = 1;
	}
	sort(e + 1, e + m + 1);
	clear();
	for (int i = 1; i <= m; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (fu == fv) continue;
		fa[fv] = fu;
		e[i].tag = 0;
		pre.push_back(e[i]);
		cnt++;
		if (cnt == n - 1) break;
	}

	clear();
	for (int i = 1; i <= m; i++) {
		if (!e[i].tag) continue;
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (fu == fv) continue;
		fa[fv] = fu;

		son[u].push_back({ v,e[i].w });
		son[v].push_back({ u,e[i].w });

		cnt++;
		if (cnt == n - 1) break;
	}
	if (cnt < n - 1) {
		cout << -1;
		return 0;
	}

	int rt = 1;
	dfs(rt, 0);
	val[rt] = -INF;
	fun(rt, 0);

	ll ans = 0;
	for (int i = 0; i < pre.size(); i++) {
		int s = pre[i].u, t = pre[i].v;
		//cout << s << " " << t << " " << pre[i].w << " ";
		ll tmp = (ll)get(s, t);
		//cout << tmp << " " << endl;
		ans += tmp + 1LL - pre[i].w;
	}
	cout << ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9820kb

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

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: 1ms
memory: 9752kb

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: 1ms
memory: 7816kb

input:

2 1
1 2 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 22ms
memory: 16532kb

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
Runtime Error

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: