QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314343 | #8134. LCA Counting | tuanlinh123 | WA | 4ms | 14948kb | C++20 | 1.3kb | 2024-01-25 15:49:54 | 2024-01-25 15:49:55 |
Judging History
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'