QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464010#2524. Dessert Caféyzkkai#WA 52ms20292kbC++201.7kb2024-07-05 17:17:342024-07-05 17:17:34

Judging History

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

  • [2024-07-05 17:17:34]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:20292kb
  • [2024-07-05 17:17:34]
  • 提交

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'