/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 5ms 4.996 MiB
#2 Accepted 5ms 5.086 MiB
#3 Accepted 5ms 5.0 MiB
#4 Accepted 5ms 5.0 MiB
#5 Accepted 5ms 5.086 MiB
#6 Accepted 5ms 4.996 MiB
#7 Accepted 14ms 7.777 MiB
#8 Accepted 138ms 31.617 MiB
#9 Accepted 8ms 6.625 MiB
#10 Accepted 34ms 17.137 MiB
#11 Accepted 64ms 27.75 MiB
#12 Accepted 79ms 35.16 MiB
#13 Accepted 31ms 16.191 MiB
#14 Accepted 59ms 27.277 MiB
#15 Runtime Error 54ms 27.742 MiB
#16 Runtime Error 69ms 31.555 MiB
#17 Wrong Answer 99ms 34.059 MiB
#18 Wrong Answer 102ms 33.586 MiB
#19 Wrong Answer 103ms 33.285 MiB
#20 Accepted 112ms 37.363 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(){
	ps_1st[0]=-1;
	ps_2nd[0]=-1;
	ss_1st[n+1]=-1;
	ss_2nd[n+1]=-1;
	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];
		_3rd[i]=-1;
		_2nd[i]=-1;
		_1st[i]=-1;
	}
	dfs(1);
	init();
	int u;
	while(q--){
		cin>>u;
		int res=0;
		int maxl=-1;
		int scdl=-1;
		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(_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:54:13
评测时间
2024-06-27 18:54:13
评测机
分数
75
总耗时
1008ms
峰值内存
37.363 MiB