QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464010 | #2524. Dessert Café | yzkkai# | WA | 52ms | 20292kb | C++20 | 1.7kb | 2024-07-05 17:17:34 | 2024-07-05 17:17:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int dfs1(int cur, int par, vector<int> &cnt, vector<vector<pii>> &edges) {
for (auto &[w, nxt] : edges[cur]) {
if (nxt == par) continue;
cnt[cur] += dfs1(nxt, cur, cnt, edges);
}
return cnt[cur];
}
set<int> ans;
void dfs2(int cur, int par, int pre, vector<int> &cnt, vector<vector<pii>> &edges) {
int sum = pre;
for (auto &[w, nxt] : edges[cur]) {
if (nxt == par) continue;
sum += cnt[nxt] > 0;
}
if (sum >= 2) ans.emplace(cur);
for (auto &[w, nxt] : edges[cur]) {
if (nxt == par) continue;
dfs2(nxt, cur, (sum > 0), cnt, edges);
}
return;
}
inline void solve() {
int n, k;
cin >> n >> k;
vector<vector<pii>> edges(n + 1);
for (int i = 1, u, v, w; i < n; ++i) {
cin >> u >> v >> w;
edges[u].emplace_back(w, v);
edges[v].emplace_back(w, u);
}
ans.clear();
vector<int> labs(k), cnt(n + 1);
for (int &i : labs) {
cin >> i;
cnt[i] = 1;
ans.emplace(i);
}
for (int i = 1; i <= n; ++i)
sort(edges[i].begin(), edges[i].end());
for (int i : labs) {
if (size(edges[i]) > 1 && edges[i][0].first == edges[i][1].first) continue;
if (size(edges[edges[i][0].second]) == 1)
ans.emplace(edges[i][0].second);
}
dfs1(1, 0, cnt, edges);
dfs2(1, 0, 0, cnt, edges);
cout << size(ans) << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
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: 0
Accepted
time: 48ms
memory: 18940kb
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:
98605
result:
ok single line: '98605'
Test #3:
score: -100
Wrong Answer
time: 52ms
memory: 20292kb
input:
100000 50000 94951 20623 136 20623 86149 475 86149 27364 745 27364 17265 605 17265 33632 110 33632 14073 207 14073 53697 5 53697 49015 30 49015 35727 469 35727 45004 949 45004 49608 812 49608 73211 160 73211 83010 767 83010 90180 731 90180 27419 363 27419 85567 327 85567 2670 383 2670 62387 399 6238...
output:
100000
result:
wrong answer 1st lines differ - expected: '99999', found: '100000'