QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591132#7937. Fast XORtingucup-team3519#WA 0ms3552kbC++171.3kb2024-09-26 14:23:152024-09-26 14:23:16

Judging History

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

  • [2024-09-26 14:23:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3552kb
  • [2024-09-26 14:23:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define V vector
#define all1(x) (x).begin() + 1, (x).end()
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> pi;

void solve() {
    int n; cin >> n;
    if(n == 1) {
        cout << 2 << endl;
        return;
    }
    V<V<int>> e(n + 1);
    V<int> f(n + 1);
    for(int i =1 ; i < n; i++) {
        int a, b; cin >> a >> b;
        e[a].pb(b);
        e[b].pb(a);
    }
    V<int> dep(n + 1);
    V<int> d(n + 1);
    auto dfs = [&](int x, int p, auto dfs) -> void {
        f[x] = p;
        if(p) d[p]++;
        dep[x] = dep[p] + 1;
        for(auto y : e[x]) {
            if(y == p) continue;
            dfs(y, x, dfs);
        }
    };
    dfs(1, 0, dfs);
    multiset<pi> st;
    for(int i = 1; i <= n; i++) {
        st.insert({dep[i], i});
    }
    int ans = 0;
    while(st.size()) {
        auto it = prev(st.end());
        int x = it->se;
        if(d[f[x]] == 1) {
            st.erase(it), st.erase({dep[f[x]], f[x]});
            ans++;
        } else {
            d[f[x]]--;
            st.erase(it);
            ans += 2;
        }
    }
    cout << ans << endl;

}
int main() {
    // int t; cin >> t;
    int t = 1;
    while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3552kb

input:

8
0 1 3 2 5 4 7 6

output:

16

result:

wrong answer 1st numbers differ - expected: '2', found: '16'