QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770341#6619. Line Graph Matchinglonelywolf#WA 197ms36516kbC++201.9kb2024-11-21 21:30:032024-11-21 21:30:10

Judging History

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

  • [2024-11-21 21:30:10]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:36516kb
  • [2024-11-21 21:30:03]
  • 提交

answer

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

#define int long long  

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

	int n, m;
	cin >> n >> m;

	vector<vector<pair<int, int>>> adj(n + 1);
	vector<tuple<int, int, int>> e;
	map<pair<int, int>, int> t;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		sum += w;
		t[{x, y}] = w;
		t[{y, x}] = w;
		e.push_back({x, y, w});
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}

	if (m % 2 == 0) {
		cout << sum << "\n";
		return 0;
	}

	vector<int> low(n + 1), dfn(n + 1), fa(n + 1);
	vector<int> cnt(n + 1);
	set<pair<int, int>> br;
	int tim = 0;
	function<void(int, int)> dfs = [&](int x, int f) {
		fa[x] = f;
		low[x] = dfn[x] = ++tim;
		for (auto [y, w] : adj[x]) {
			if (!dfn[y]) {
				dfs(y, x);
				low[x] = min(low[x], low[y]);
				if (low[y] > dfn[x]) {
					br.insert({x, y});
				}
			} else if (dfn[y] < dfn[x] && y != f) {
				low[x] = min(low[x], dfn[y]);
			}
		}
	};
	dfs(1, 0);

	vector<int> a(n + 2);
	for (int i = 1; i <= n; i++) {
		a[low[i]] += adj[i].size();
	}
	// for (int i = 1; i <= n; i++) {
	// 	cout << a[i] << " \n"[i == n];
	// }
	for (int i = n; i >= 0; i--) {
		a[i] += a[i + 1];
	}
	for (int i = 0; i <= n; i++) {
		a[i] = (a[i] - 1) / 2;
	}
	
	// for (int i = 1; i <= n; i++) {
	// 	cout << dfn[i] << " \n"[i == n];
	// }
	// for (int i = 1; i <= n; i++) {
	// 	cout << low[i] << " \n"[i == n];
	// }
	// for (int i = 1; i <= n; i++) {
	// 	cout << a[i] << " \n"[i == n];
	// }

	int mn = 1e18;
	for (auto [x, y, w] : e) {
		if (!br.count({x, y}) && !br.count({y, x})) {
			mn = min(mn, w);
		} else {
			if (br.count({x, y})) {
				if (a[dfn[x] + 1] % 2 == 0) {
					mn = min(mn, w);
				}
			} else {
				if (a[dfn[y] + 1] % 2 == 0) {
					mn = min(mn, w);
				}
			}
		} 
	}

	cout << sum - mn << "\n";
 
    return 0;
}  
  

詳細信息

Test #1:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #2:

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

input:

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

output:

12

result:

ok 1 number(s): "12"

Test #3:

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

input:

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

output:

14

result:

ok 1 number(s): "14"

Test #4:

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

input:

3 2
1 2 1
2 3 2

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

3 3
1 2 3
2 3 1
3 1 2

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #7:

score: -100
Wrong Answer
time: 197ms
memory: 36516kb

input:

100000 99999
54273 5761 179909546
6472 21601 924153552
610 22693 767540137
37784 2454 951330587
24457 93770 781030280
36098 27 448166069
21292 43394 244510129
58047 86330 869927899
18770 83124 20504174
24036 92856 8370757
92492 21932 734860719
43776 77624 226721931
15746 70738 429430538
71204 87185 ...

output:

49946352897973

result:

wrong answer 1st numbers differ - expected: '49946352904479', found: '49946352897973'