QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504705#9101. Zayin and BusXunwuqishi#AC ✓195ms15340kbC++201.3kb2024-08-04 15:06:522024-08-04 15:06:52

Judging History

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

  • [2024-08-04 15:06:52]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:15340kb
  • [2024-08-04 15:06:52]
  • 提交

answer

#include<bits/stdc++.h>
#define Alex std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define int long long
#define double long double
const int QAQ = 0;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
std::vector<int> G[500005];
int Dep[500005];
inline bool cmp(std::pair<int,int> x,std::pair<int,int> y)
{
	if(x.second < y.second) return true;else return false;
}
inline bool cmpp(int x,int y)
{
	return x > y;
}
inline void dfs(int u,int fa)
{
	Dep[u] = Dep[fa] + 1;
	for(auto v : G[u])
	{
		if(v == fa) continue;
		dfs(v,u);
	}
}
signed main()
{
	Alex;
	int _;
	_ = 1;
	std::cin>>_;
	while(_--)
	{
		int n;
		std::cin>>n;
		int f[n + 10],a[n + 10];
		std::pair<int,int> p[n + 10];
		for(int i = 0;i <= n + 1;i++) Dep[i] = 0;
		for(int i = 1;i <= n;i++) G[i].clear();
		for(int i = 1;i <= n - 1;i++) 
		{
			std::cin>>f[i];
			G[f[i]].push_back(i + 1);
			G[i + 1].push_back(f[i]);
		}
		for(int i = 1;i <= n;i++) std::cin>>a[i];
		for(int i = 1;i <= n;i++)
		{
			p[i].first = a[i];
			p[i].second = a[i] + i;
		}
		std::sort(p + 1,p + n + 1,cmp);
		dfs(1,0);
		std::sort(Dep + 1,Dep + n + 1,cmpp);
		int ans = 0;
		for(int i = 1;i <= n;i++) ans = std::max(ans,Dep[i] + p[i].second - 1);
		std::cout<<ans<<'\n';
	}
	return QAQ;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

14
1
1
1
2
1
3
2
1
1 1
2
1
1 2
2
1
2 1
2
1
1 3
2
1
3 1
2
1
1 4
2
1
4 1
3
1 1
1 1 1
3
1 2
1 1 1
3
1 1
1 3 2
3
1 2
1 3 2

output:

2
3
4
3
4
4
5
4
6
5
4
4
6
6

result:

ok 14 lines

Test #2:

score: 0
Accepted
time: 195ms
memory: 15340kb

input:

15
1000
1 2 2 1 1 1 4 8 1 7 7 7 9 3 4 7 15 18 18 4 6 11 19 7 6 1 9 13 2 21 28 6 17 24 24 2 28 5 32 24 23 8 3 26 15 28 25 34 46 41 33 16 46 11 7 2 13 53 12 59 52 53 51 52 31 41 63 18 55 49 55 62 15 19 23 67 18 37 2 4 23 75 58 55 14 84 20 3 7 89 82 15 53 77 60 25 97 69 5 40 54 24 72 10 87 90 99 43 71 ...

output:

98572828
100088663
99870474
100076153
99995412
100076982
99971239
100079684
99928633
100093408
99432584
100093568
99620300
100058966
99565256

result:

ok 15 lines