QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#706007 | #5154. ETA | magicman1235 | WA | 2ms | 11140kb | C++14 | 1.7kb | 2024-11-03 05:33:14 | 2024-11-03 05:33:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, ans;
vector<int> adj[MAXN];
int l[MAXN], r[MAXN];
int depth[MAXN], subtreeSize[MAXN];
void update(int node)
{
depth[node] = max(depth[l[node]], depth[r[node]]) + 1;
subtreeSize[node] = subtreeSize[l[node]] + subtreeSize[r[node]] + 1;
}
void dfs(int node, int parent)
{
depth[node] = 1;
subtreeSize[node] = 1;
for (int v : adj[node])
{
if (v == parent)
{
continue;
}
if (!l[node])
{
l[node] = v;
}
else
{
r[node] = v;
}
dfs(v, node);
update(node);
}
}
void remove(int node, int dep)
{
if (!node)
{
return;
}
if (dep == 0)
{
ans -= subtreeSize[l[node]] + subtreeSize[r[node]];
l[node] = 0;
r[node] = 0;
depth[node] = 1;
subtreeSize[node] = 1;
return;
}
remove(l[node], dep - 1);
remove(r[node], dep - 1);
update(node);
}
void solve(int node)
{
if (!node)
{
return;
}
solve(l[node]);
solve(r[node]);
if (depth[l[node]] > depth[r[node]])
{
swap(l[node], r[node]);
}
if (depth[r[node]] - depth[l[node]] > 1)
{
remove(r[node], depth[l[node]]);
}
update(node);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
ans = n;
for (int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0);
solve(1);
cout << n - ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11140kb
input:
1/2
output:
0
result:
wrong answer Integer parameter [name=n] equals to 0, violates the range [1, 1000000]