QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310171#8134. LCA Countingucup-team992#WA 1ms5592kbC++172.5kb2024-01-21 06:28:132024-01-21 06:28:13

Judging History

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

  • [2024-01-21 06:28:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5592kb
  • [2024-01-21 06:28:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define F first
#define S second
typedef int uci;
#define int long long
int diff[200001];
int has[200001];
bool leaf[200001];
int lc;
void pre(int v, vector<vector<int>> &adj){
    if(leaf[v]){
        has[v] = 1;
        return;
    }
    for(int i : adj[v]){
        pre(i, adj);
        has[v] += has[i];
    }
}

void recurse(int v, vector<int> &ins, vector<vector<int>> &adj){
    int ones = adj[v].size();
    ones -= 2;
    vector<pair<vector<int>, int>> comp(adj[v].size());
    for(int i{}; i < adj[v].size(); ++i){
        recurse(adj[v][i], comp[i].F, adj);
        comp[i].S = has[adj[v][i]];
    }
    sort(comp.begin(), comp.end());
    int run{};
    int c{};
    for(int i{}; i < adj[v].size(); ++i){
        if(comp[i].F.empty())
            continue;
        if(c < ones){
            for(int j : comp[i].F)
                ins.push_back(j+run);
            ins.push_back(run+comp[i].S);
            c++;
        }else{
            for(int j : comp[i].F)
                ins.push_back(j+run);
        }
        run += comp[i].S;
    }
    for(int i{}; i < adj[v].size(); ++i){
        if(comp[i].F.size())
            continue;

        if(c < ones){
            for(int j : comp[i].F)
                ins.push_back(j+run);
            ins.push_back(run+comp[i].S);
            c++;
        }else{
            for(int j : comp[i].F)
                ins.push_back(j+run);
        }
        run += comp[i].S;
    }
    /*
    cout << "vertex: " << v << '\n';
    for(int i : ins)
        cout << i << ' ';
    cout << '\n';
    */
}

void solve(){
    memset(has, 0, sizeof(has));
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> par(n);
    for(int i{1}; i < n; ++i){
        cin >> par[i];
        par[i]--;
        adj[par[i]].push_back(i);
    }
    memset(leaf, 0, sizeof(leaf));
    int tot = n;
    lc = 0;
    for(int i{}; i < n; ++i){
        if(adj[i].empty()){
            leaf[i] = true;
            lc++;
        }
        if(adj[i].size() == 1)
            tot--;
    }
    pre(0, adj);
    for(int i{}; i < n; ++i)
        diff[i] = 2;
    vector<int> ones;
    recurse(0, ones, adj);
    for(int i : ones){
        diff[lc-i] = 1;
    }
    vector<int> out(lc, tot);
    for(int i = lc-1; i >= 0; --i){
        out[i] = tot;
        tot -= diff[i];
    }
    for(int i : out)
        cout << i << ' ';
    cout << '\n';
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 5592kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 4 5 6 8 9 

result:

wrong answer 3rd numbers differ - expected: '5', found: '4'