QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#538100#8134. LCA CountingIstleminWA 0ms3828kbC++141.1kb2024-08-31 00:08:442024-08-31 00:08:44

Judging History

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

  • [2024-08-31 00:08:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-08-31 00:08:44]
  • 提交

answer

#include<bits/stdc++.h>

#pragma GCC optimize ("Ofast")
using namespace std;

#define rep(i,a,b) for(ll i = a; i<b;i++)
#define rrep(i,a,b) for(ll i = b-1; i>=a;i--)
#define trav(x,a) for(auto &x: a)
#define all(v) v.begin(),v.end()
#define sz(v) ll(v.size())

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    ll n; cin>>n;

    vector<vl> e(n);
    rep(i,1,n) {
        ll p; cin>>p;
        e[p-1].push_back(i);
    }

    ll leaves = 0;

    function<ll(ll)> rec = [&](ll v) {
        if(sz(e[v])==0){
            leaves ++;
            return 1ll;
        }
        vl chAns;
        for(auto u: e[v]){
            chAns.push_back(rec(u));
        }
        sort(all(chAns));
        ll ans = chAns.back();
        if(sz(chAns)>1) ans += chAns[sz(chAns)-2];
        return ans;
    };

    ll goods = rec(0);

    rep(i,0,goods){
        cout<<i*2+1<<" ";
    }
    rep(i,goods,leaves){
        cout<<goods*2+(i-goods)<<" ";
    }
    cout<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

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: 0ms
memory: 3592kb

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

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: 0ms
memory: 3828kb

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: 0ms
memory: 3640kb

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 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 10...

result:

wrong answer 6th numbers differ - expected: '10', found: '9'