QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461064 | #8481. Cooperative game on a tree | Lynkcat# | WA | 2ms | 11836kb | C++14 | 1.4kb | 2024-07-02 15:43:42 | 2024-07-02 15:43:42 |
Judging History
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'