QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#591132 | #7937. Fast XORting | ucup-team3519# | WA | 0ms | 3552kb | C++17 | 1.3kb | 2024-09-26 14:23:15 | 2024-09-26 14:23:16 |
Judging History
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'