比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 AAWWWWWTTT
题目名称 van玩galgame 最终得分 20
用户昵称 Lesater 运行时间 4.366 s
代码语言 C++ 内存使用 43.88 MiB
提交时间 2022-09-05 21:20:06
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int n;
  5. ll rrrr;
  6. struct data{
  7. int to;
  8. ll len;
  9. ll all;
  10. };
  11. struct Node{
  12. vector<data> ch;
  13. ll b1,b2;
  14. };
  15. Node tree[1000000];
  16. int dfs(int now,ll cnt)
  17. {
  18. ll ans=cnt;
  19. if(tree[now].ch.size()==0) return cnt;
  20. for(int i=0;i<tree[now].ch.size();++i)
  21. {
  22. tree[now].ch[i].all=dfs(tree[now].ch[i].to,tree[now].ch[i].len);
  23. ans=max(ans,cnt+tree[now].ch[i].all);
  24. }
  25. return ans;
  26. }
  27. bool cmp(data a,data b)
  28. {
  29. return a.all>b.all;
  30. }
  31. void best(int now,int asd)
  32. {
  33. if(tree[now].ch.size()==0) return;
  34. rrrr=max(rrrr,asd+tree[now].b1+tree[now].b2);
  35. for(int i=0;i<tree[now].ch.size();++i)
  36. best(tree[now].ch[i].to,asd+tree[now].ch[i].len);
  37. return;
  38. }
  39. int main()
  40. {
  41. freopen("galgame.in","r",stdin);
  42. freopen("galgame.out","w",stdout);
  43. cin>>n;
  44. for(int i=1;i<=n;++i)
  45. {
  46. int k;
  47. cin>>k;
  48. for(int j=1;j<=k;++j)
  49. {
  50. data a;
  51. cin>>a.len>>a.to;
  52. a.all=0;
  53. tree[i].ch.push_back(a);
  54. }
  55. }
  56. dfs(1,0);
  57. for(int i=1;i<=n;++i)
  58. {
  59. for(int j=0;j<tree[i].ch.size();++j)
  60. {
  61. if(tree[i].ch[j].all>tree[i].b2)
  62. {
  63. tree[i].b2=tree[i].ch[j].all;
  64. if(tree[i].b2>tree[i].b1) swap(tree[i].b1,tree[i].b2);
  65. }
  66. }
  67. }
  68. best(1,0);
  69. cout<<rrrr<<endl;
  70. return 0;
  71. }