QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#504705 | #9101. Zayin and Bus | Xunwuqishi# | AC ✓ | 195ms | 15340kb | C++20 | 1.3kb | 2024-08-04 15:06:52 | 2024-08-04 15:06:52 |
Judging History
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