QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314343#8134. LCA Countingtuanlinh123WA 4ms14948kbC++201.3kb2024-01-25 15:49:542024-01-25 15:49:55

Judging History

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

  • [2024-01-25 15:49:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:14948kb
  • [2024-01-25 15:49:54]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

ll cnt;
vector <ll> A[200005];
multiset <ll> s[200005];

void dfs(ll u)
{
    if (A[u].size()==0) {cnt++; return;}
    if (A[u].size()==1)
    {
        dfs(A[u][0]);
        swap(s[A[u][0]], s[u]);
        return;
    }
    for (ll v:A[u])
    {
        dfs(v);
        if (s[v].size()>s[u].size())
            swap(s[v], s[u]);
        for (ll i:s[v]) s[u].insert(i);
    }
    if (s[u].size()==0) s[u].insert(1);
    else
    {
        ll val=*prev(s[u].end());
        s[u].erase(prev(s[u].end()));
        s[u].insert(val+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=2; i<=n; i++)
    {
        ll x; cin >> x;
        A[x].pb(i);
    }
    dfs(1); vector <ll> ans, c; ans.pb(1);
    for (ll i:s[1]) c.pb(i);
    reverse(c.begin(), c.end());
    for (ll i:c)
    {
        for (ll j=0; j<i; j++)
            ans.pb(2);
        ans.pb(1);
    }
    while (ans.size()<cnt) ans.pb(1);
    ll crr=0;
    for (ll i:ans)
    {
        crr+=i;
        cout << crr << " ";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 14948kb

input:

7
1 1 2 4 2 2

output:

1 3 5 6 

result:

ok 4 number(s): "1 3 5 6"

Test #2:

score: 0
Accepted
time: 3ms
memory: 12900kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 5 6 7 8 9 

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 14448kb

input:

10
1 2 2 4 5 6 1 2 4

output:

1 3 5 7 8 

result:

ok 5 number(s): "1 3 5 7 8"

Test #4:

score: 0
Accepted
time: 3ms
memory: 13108kb

input:

10
1 2 3 3 3 5 6 4 9

output:

1 3 4 

result:

ok 3 number(s): "1 3 4"

Test #5:

score: -100
Wrong Answer
time: 4ms
memory: 14120kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...

output:

1 3 5 6 8 9 11 12 14 15 17 18 20 21 23 24 26 27 29 30 32 33 35 36 38 39 41 42 44 45 47 48 50 51 53 54 56 57 59 60 62 63 65 66 68 69 71 72 74 75 77 78 80 81 83 84 86 87 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124...

result:

wrong answer 4th numbers differ - expected: '7', found: '6'