QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706007#5154. ETAmagicman1235WA 2ms11140kbC++141.7kb2024-11-03 05:33:142024-11-03 05:33:14

Judging History

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

  • [2024-11-03 05:33:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11140kb
  • [2024-11-03 05:33:14]
  • 提交

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";
}

詳細信息

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]