QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474059#6745. Delete the Treek1nsomWA 3ms14388kbC++171.7kb2024-07-12 15:50:542024-07-12 15:50:55

Judging History

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

  • [2024-07-12 15:50:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:14388kb
  • [2024-07-12 15:50:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
#define endl '\n'
int n, ctr = -1, cnt = 0, tot, si[N] = {0};
bool del[N], vis[N];
vector<int> e[N], ans[N];
void dfs(int u, int fa = 0)
{
    si[u] = 1;
    int mss = 0;
    for (auto to : e[u])
        if (!vis[to] && to != fa)
        {
            dfs(to, u);
            if (ctr != -1)
                return;
            si[u] += si[to];
            mss = max(mss, si[to]);
        }
    mss = max(mss, tot - si[u]);
    if (mss <= tot / 2)
    {
        ctr = u;
        si[fa] = tot - si[u];
    }
}
void dfs2(int u, int fa, int flag)
{
    for (auto to : e[u])
        if (!vis[to] && to != fa)
        {
            if (!del[to] && flag)
            {
                ans[cnt].push_back(to);
                del[to] = 1;
            }
            dfs2(to, u, flag ^ 1);
        }
}
void func(int u)
{
    if (!del[u])
    {
        ans[++cnt].push_back(u);
        del[u] = 1;
    }
    for (auto to : e[u])
        if (!vis[to])
            dfs2(to, u, 1);
    vis[u] = 1;
    for (auto to : e[u])
        if (!vis[to])
        {
            tot = si[to];
            ctr = -1;
            dfs(to);
            func(ctr);
        }
}
signed main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    tot = n;
    ctr = -1;
    dfs(1, 0);
    func(ctr);
    cout << cnt << endl;
    for (int i = 1; i <= cnt; cout << endl, i++)
    {
        cout << ans[i].size() << ' ';
        for (auto v : ans[i])
            cout << v << ' ';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14388kb

input:

5
1 2
1 3
1 4
4 5

output:

4
2 1 5 
1 2 
1 3 
1 4 

result:

ok 

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 14084kb

input:

500
183 443
32 443
334 443
254 443
331 443
348 443
54 443
430 443
275 443
410 443
360 443
443 468
140 443
179 443
93 443
327 443
128 443
365 443
122 443
43 443
46 443
399 443
398 443
269 443
130 443
227 443
412 443
61 443
295 443
98 443
30 443
197 443
397 443
95 443
192 443
266 443
48 443
310 443
28...

output:

500
1 443 
1 183 
1 32 
1 334 
1 254 
1 331 
1 348 
1 54 
1 430 
1 275 
1 410 
1 360 
1 468 
1 140 
1 179 
1 93 
1 327 
1 128 
1 365 
1 122 
1 43 
1 46 
1 399 
1 398 
1 269 
1 130 
1 227 
1 412 
1 61 
1 295 
1 98 
1 30 
1 197 
1 397 
1 95 
1 192 
1 266 
1 48 
1 310 
1 283 
1 127 
1 123 
1 7 
1 154 
...

result:

wrong answer Integer 500 violates the range [0, 10]