QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464473 | #2524. Dessert Café | KryptonK | WA | 29ms | 20560kb | C++20 | 1.4kb | 2024-07-06 09:27:53 | 2024-07-06 09:27:53 |
Judging History
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'