/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer Read 102, expect 94. 7ms 5.023 MiB
#2 Accepted 7ms 5.023 MiB
#3 Accepted 6ms 5.023 MiB
#4 Wrong Answer Read 70, expect 62. 7ms 5.023 MiB
#5 Accepted 6ms 5.246 MiB
#6 Accepted 6ms 5.246 MiB
#7 Wrong Answer Read 1098, expect 1000. 12ms 6.562 MiB
#8 Accepted 19ms 7.773 MiB
#9 Wrong Answer Read 1098, expect 1000. 50ms 16.801 MiB
#10 Wrong Answer Read 1098, expect 1000. 90ms 26.773 MiB
#11 Accepted 149ms 31.734 MiB
#12 Wrong Answer Read 10006, expect 10000. 47ms 14.855 MiB
#13 Wrong Answer Read 1098, expect 1000. 114ms 34.023 MiB
#14 Wrong Answer Read 999995, expect 999994. 50ms 25.023 MiB
#15 Wrong Answer Read 1029976, expect 999994. 133ms 34.816 MiB
#16 Wrong Answer Read 10280321, expect 9999936. 161ms 45.023 MiB
#17 Wrong Answer Read 1048, expect 1000. 148ms 34.25 MiB
#18 Wrong Answer Read 1008378, expect 999996. 140ms 36.297 MiB
#19 Wrong Answer Read 2098, expect 2000. 154ms 33.816 MiB
#20 Wrong Answer Read 5988, expect 5000. 153ms 33.488 MiB

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=2e5+10;
int n,q;
int fa[Max];
int b[Max],l[Max];
vector<int> child[Max];
int dfn[Max];
int last[Max];
int bb[Max];
int ll[Max];
int _1st[Max];
int _2nd[Max];
int _3rd[Max];
int cnt_st[Max];
void dfs(int u){
	dfn[u]=++dfn[0];
	_1st[u]=b[u];
	cnt_st[u]=1;
	bb[dfn[u]]=b[u];
	ll[dfn[u]]=l[u];
	for(auto v:child[u]){
		dfs(v);
		///////////////////////////
		if(_1st[v]>=_1st[u]){
			if(_1st[v]==_1st[u]){
				cnt_st[u]+=cnt_st[v];
			} else {
				cnt_st[u]=1;
				_3rd[u]=_2nd[u];
				_2nd[u]=_1st[u];
				_1st[u]=_1st[v];
			}
		} else if(_1st[v]>=_2nd[u]){
			if(_1st[v]>_2nd[u]){
				_3rd[u]=_2nd[u];
				_2nd[u]=_1st[v];
			}
		} else if(_1st[v]>_3rd[u]){
			_3rd[u]=_1st[v];
		}
		///////////////////////////
		if(_2nd[v]>=_2nd[u]){
			if(_2nd[v]>_2nd[u]){
				_3rd[u]=_2nd[u];
				_2nd[u]=_2nd[v];
			}
		} else if(_2nd[v]>_3rd[u]){
			_3rd[u]=_2nd[v];
		}
		//////////////////////////
		if(_3rd[v]>_3rd[u]){
			_3rd[u]=_3rd[v];
		}
	}
	last[u]=dfn[0];
}
int ps_1st[Max];
int ps_2nd[Max];
int ss_1st[Max];
int ss_2nd[Max];
void init(){
	for(int i=1;i<=n;i++){
		ps_1st[i]=ps_1st[i-1];
		ps_2nd[i]=ps_2nd[i-1];
		if(ll[i]==ps_1st[i]){
			continue;
		}
		if(ll[i]>ps_1st[i]){
			ps_2nd[i]=ps_1st[i];
			ps_1st[i]=ll[i];
		} else if(ll[i]>ps_2nd[i]){
			ps_2nd[i]=ll[i];
		}
	}
	for(int i=n;i>=1;i--){
		ss_1st[i]=ss_1st[i+1];
		ss_2nd[i]=ss_2nd[i+1];
		if(ll[i]==ss_1st[i]){
			continue;
		}
		if(ll[i]>ss_1st[i]){
			ss_2nd[i]=ss_1st[i];
			ss_1st[i]=ll[i];
		} else if(ll[i]>ss_2nd[i]){
			ss_2nd[i]=ll[i];
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		child[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>b[i]>>l[i];
	}
	dfs(1);
	init();
	int u;
	while(q--){
		cin>>u;
		int res=0;
		int maxl=0;
		int scdl=0;
		if(ps_1st[dfn[u]-1]==ss_1st[last[u]+1]){
			maxl=ps_1st[dfn[u]-1];
			scdl=max(ps_2nd[dfn[u]-1],ss_2nd[last[u]+1]);
		} else {
			if(ps_1st[dfn[u]-1]>ss_1st[last[u]+1]){
				maxl=ps_1st[dfn[u]-1];
				scdl=max(ps_2nd[dfn[u]-1],ss_1st[last[u]+1]);
			} else {
				maxl=ss_1st[last[u]+1];
				scdl=max(ps_1st[dfn[u]-1],ss_2nd[last[u]+1]);
			}
		}
		if(_2nd[u]){
			res=max(res,_2nd[u]);
			if(maxl){
				if(_2nd[u]+maxl>_1st[u]){
					res=max(res,_1st[u]);
					if(_3rd[u]){
						res=max(res,_3rd[u]+maxl);
					}
				}
				if(_2nd[u]+maxl==_1st[u]){
					if(_3rd[u]){
						res=max(res,_3rd[u]+maxl);
					}
					if(scdl){
						res=max(res,_2nd[u]+scdl);
					}
				}
				if(_2nd[u]+maxl<_1st[u]){
					res=max(_2nd[u]+maxl,res);
				}
			}
		}
		if(cnt_st[u]>1&&maxl){
			res=max(res,_1st[u]);
		}
		cout<<res<<'\n';
	}
	return 0;
}

/*
  time:
  mem:
  
  7 3
  1 2 1 2 4 4
  3 0
  1 3
  2 0
  5 2
  4 1
  3 1
  2 2
  1
  2
  4
  
  5 1
  1 2 3 4
  1 1
  1 1
  1 1
  1 1
  1 1
  2
 */

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2024-06-27 18:45:35
评测时间
2024-06-27 18:45:35
评测机
分数
30
总耗时
1467ms
峰值内存
45.023 MiB