QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464473#2524. Dessert CaféKryptonKWA 29ms20560kbC++201.4kb2024-07-06 09:27:532024-07-06 09:27:53

Judging History

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

  • [2024-07-06 09:27:53]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:20560kb
  • [2024-07-06 09:27:53]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
using LL = long long;

void O_o() {
	int n, k;
	cin >> n >> k;
	
	vector<vector<int>> adj(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		u--, v--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}

	vector<int> tag(n), ok(n);
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		x--;
		tag[x] = ok[x] = 1;
	}
	
	vector<int> sub(n);
	auto dfs = [&] (auto dfs, int x, int lst) -> void {
		if (tag[x]) {
			sub[x] = 1;
		}
		for (auto y : adj[x]) {
			if (y == lst) {
				continue;
			}
			dfs(dfs, y, x);
			if (sub[y]) {
				sub[x] = 1;
			}
		}
	};
	dfs(dfs, 0, -1);

	auto dfs2 = [&] (auto dfs2, int x, int lst, int f) -> void {
		vector<int> a;
		for (auto y : adj[x]) {
			if (y == lst) {
				continue;
			}
			if (sub[y]) {
				a.push_back(y);
			}
		}
		if (a.size() > 1 || (a.size() == 1 && f)) {
			ok[x] = 1;
		}
		for (auto y : adj[x]) {
			if (y == lst) {
				continue;
			}
			int tr = f;
			if (tag[x] || a.size() > 2 || (a.size() == 1 && a[0] != y)) {
				tr = 1;
			}
			dfs2(dfs2, y, x, tr);
		}
	};
	dfs2(dfs2, 0, -1, 0);
	
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (ok[i]) {
			res++;
		}
	}
	cout << res << '\n';
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
		
	while (t--) {
		O_o();
	}

	return 0;
}

詳細信息

Test #1:

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

input:

9 2
1 2 8
2 4 7
4 3 6
4 6 4
5 6 3
6 7 2
6 9 5
9 8 6
1 8

output:

6

result:

ok single line: '6'

Test #2:

score: -100
Wrong Answer
time: 29ms
memory: 20560kb

input:

100000 100
41922 34014 139
34014 84836 956
84836 7781 847
7781 16771 721
16771 92902 843
92902 81424 720
81424 83534 533
83534 35753 700
35753 83842 942
83842 24433 927
24433 10546 126
10546 77395 256
77395 43977 409
43977 53104 888
53104 25245 895
25245 23079 161
23079 95499 64
95499 73702 309
7370...

output:

95281

result:

wrong answer 1st lines differ - expected: '98605', found: '95281'