QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474103#6745. Delete the Treek1nsomWA 3ms13344kbC++171.7kb2024-07-12 16:07:452024-07-12 16:07:45

Judging History

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

  • [2024-07-12 16:07:45]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13344kb
  • [2024-07-12 16:07:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define N 200005
int n, k, m, tot, top = 0, ctr = -1, si[N] = {0};
bool vis[N], del[N], instk[N];
vector<int> e[N], temp, ans[N];
void dfs(int u, int fa) // 找重心
{
    si[u] = 1;
    int mss = 0; // max subtree size
    for (auto to : e[u])
        if (!del[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 len)
{
    if (!instk[u] && len % 2 == 0)
    {
        instk[u] = 1;
        ans[top].push_back(u);
    }
    for (auto to : e[u])
        if (!del[to] && to != fa)
            dfs2(to, u, len + 1);
}
void func(int u)
{
    if (!instk[u])
    {
        top++;
        ans[top].push_back(u);
    }
    for (auto to : e[u])
        if (!del[to])
            dfs2(to, u, 1);
    del[u] = 1;
    for (auto to : e[u])
        if (!del[to])
        {
            tot = si[to];
            ctr = -1;
            dfs(to, 0);
            func(ctr);
        }
}
signed main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    tot = n;
    ctr = -1;
    dfs(1, 0);
    func(ctr);
    cout << top << endl;
    for (int i = 1; i <= top; i++)
    {
        cout << ans[i].size() << ' ';
        for (auto to : ans[i])
            cout << to << ' ';
        cout << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 13344kb

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]