1415 | 2022. 09. 09 09:35:31 | kicsiboglar | Színes fa | cpp11 | Elfogadva 50/50 | 194ms | 49140 KiB |
#include <iostream>
#include <vector>
#include <deque>
#define ll long long
using namespace std;
ll n,i,a,mini=9999999;
struct element
{
ll step,father;
vector <ll> sz;
bool leaf=false;
ll color;
};
vector <element> x;
void BFS (ll start)
{
deque<ll> v;
v.push_back(start);
x[start].step=1;
ll curr;
while (!v.empty())
{
curr=v[0];
v.pop_front();
if (x[curr].sz.empty())
{
x[curr].leaf=true;
if (x[curr].step<mini) mini=x[curr].step;
return;
}
for (auto &e:x[curr].sz)
{
x[e].step=x[curr].step+1;
v.push_back(e);
}
}
}
void paint(ll curr)
{
ll one=1;
x[curr].color=max(one,x[x[curr].father].color-1);
for (auto &e:x[curr].sz) paint(e);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
x.resize(n+1);
for (i=2;i<=n;++i)
{
cin>>a;
x[a].sz.push_back(i);
x[i].father=a;
}
BFS(1);
x[0].color=mini+1;
cout<<mini<<"\n";
paint(1);
for (i=1;i<=n;++i) cout<<x[i].color<<" ";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 6ms | 3496 KiB | |||
3 | Elfogadva | 1/1 | 2ms | 2240 KiB | |||
4 | Elfogadva | 4/4 | 2ms | 2312 KiB | |||
5 | Elfogadva | 5/5 | 75ms | 49140 KiB | |||
6 | Elfogadva | 2/2 | 100ms | 32948 KiB | |||
7 | Elfogadva | 3/3 | 100ms | 33152 KiB | |||
8 | Elfogadva | 2/2 | 112ms | 32968 KiB | |||
9 | Elfogadva | 2/2 | 103ms | 32792 KiB | |||
10 | Elfogadva | 2/2 | 108ms | 33160 KiB | |||
11 | Elfogadva | 2/2 | 123ms | 35816 KiB | |||
12 | Elfogadva | 2/2 | 167ms | 36544 KiB | |||
13 | Elfogadva | 2/2 | 137ms | 37324 KiB | |||
14 | Elfogadva | 2/2 | 140ms | 37244 KiB | |||
15 | Elfogadva | 2/2 | 142ms | 37816 KiB | |||
16 | Elfogadva | 2/2 | 140ms | 37836 KiB | |||
17 | Elfogadva | 2/2 | 173ms | 37916 KiB | |||
18 | Elfogadva | 2/2 | 160ms | 37956 KiB | |||
19 | Elfogadva | 2/2 | 174ms | 37960 KiB | |||
20 | Elfogadva | 2/2 | 192ms | 38384 KiB | |||
21 | Elfogadva | 2/2 | 194ms | 38580 KiB | |||
22 | Elfogadva | 2/2 | 165ms | 39104 KiB | |||
23 | Elfogadva | 2/2 | 172ms | 41304 KiB | |||
24 | Elfogadva | 3/3 | 179ms | 44540 KiB |