QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461064#8481. Cooperative game on a treeLynkcat#WA 2ms11836kbC++141.4kb2024-07-02 15:43:422024-07-02 15:43:42

Judging History

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

  • [2024-07-02 15:43:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11836kb
  • [2024-07-02 15:43:42]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
const int N=200005;
int n;
int dep[N],siz[N],dis[N],son[N];
poly G[N];
int mx[N];
int dp[N];
void dfs(int k)
{
    dis[k]=n;
    siz[k]=1;
    if (sz(G[k])==0) dis[k]=0;
    for (auto u:G[k])
    {
        dep[u]=dep[k]+1;
        dfs(u);
        siz[k]+=siz[u];
        if (siz[u]>siz[son[k]]) son[k]=u;
        dis[k]=min(dis[k],dis[u]+1);
    }
}
void ers(int k)
{
    mx[dep[k]]=0;
    for (auto u:G[k]) ers(u);
}
void ins(int k)
{
    mx[dep[k]]=max(mx[dep[k]],dp[k]);
    for (auto u:G[k]) ers(u);
}
void dfs1(int k)
{
    for (auto u:G[k])
        if (u!=son[k]) dfs1(u),ers(u);
    if (son[k]) dfs1(son[k]);
    for (auto u:G[k])
        if (u!=son[k]) ins(u);
    if (dis[k])
        dp[k]=mx[dep[k]+dis[k]]+1;
    mx[dep[k]]=max(mx[dep[k]],dp[k]);
}
void BellaKira()
{
    cin>>n;
    for (int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        G[x].push_back(i);
    }
    dfs(1);
    dfs1(1);
    cout<<dp[1]<<'\n';

}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1 1 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9864kb

input:

3
1 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 9864kb

input:

2
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

10
1 2 3 1 4 4 7 8 9

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 11836kb

input:

10
1 2 1 4 5 5 7 7 8

output:

1

result:

wrong answer 1st numbers differ - expected: '4', found: '1'