/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 5ms 5.004 MiB
#2 Accepted 4ms 5.094 MiB
#3 Accepted 4ms 5.008 MiB
#4 Accepted 4ms 5.082 MiB
#5 Accepted 4ms 5.109 MiB
#6 Accepted 4ms 5.02 MiB
#7 Accepted 17ms 6.727 MiB
#8 Accepted 224ms 21.207 MiB
#9 Accepted 10ms 6.414 MiB
#10 Accepted 50ms 15.473 MiB
#11 Accepted 94ms 24.531 MiB
#12 Accepted 119ms 30.887 MiB
#13 Runtime Error 22ms 16.008 MiB
#14 Runtime Error 37ms 18.109 MiB
#15 Runtime Error 50ms 20.223 MiB
#16 Runtime Error 85ms 22.305 MiB
#17 Accepted 141ms 27.613 MiB
#18 Accepted 144ms 26.262 MiB
#19 Accepted 143ms 25.434 MiB
#20 Runtime Error 76ms 28.047 MiB

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,fa[200005],maxv[200005],maxp[200005],maxv1[200005],maxp1[200005];
int maxl[200005],maxpl[200005],maxl1[200005],maxpl1[200005],ff[200005],ff1[200005],sz[200005],vis[200005];
int maxv2[200005],maxp2[200005];
vector<int> g[200005];
struct node{
	int b,l;
}a[200005];
void dfs(int u){
	maxv[u]=a[u].b;
	maxp[u]=u;
	maxl[u]=a[u].l;
	maxpl[u]=u;
	sz[u]=1;
	set<pair<int,int>> s;
	for(auto v:g[u]){
		dfs(v);
		sz[u]+=sz[v];
		if(maxv[u]<maxv[v]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv[u];
			maxp1[u]=maxp[u];
			maxv[u]=maxv[v];
			maxp[u]=maxp[v];
		}else if(maxv1[u]<maxv[v]&&maxv[v]<maxv[u]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv[v];
			maxp1[u]=maxp[v];
		}else if(maxv2[u]<maxv[v]&&maxv[v]<maxv1[u]){
			maxv2[u]=maxv[v];
			maxp2[u]=maxp[v];
		}
		if(maxv[u]<maxv1[v]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv[u];
			maxp1[u]=maxp[u];
			maxv[u]=maxv1[v];
			maxp[u]=maxp1[v];
		}else if(maxv1[u]<maxv1[v]&&maxv1[v]<maxv[u]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv1[v];
			maxp1[u]=maxp1[v];
		}else if(maxv2[u]<maxv1[v]&&maxv1[v]<maxv1[u]){
			maxv2[u]=maxv1[v];
			maxp2[u]=maxp1[v];
		}
		if(maxv[u]<maxv2[v]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv[u];
			maxp1[u]=maxp[u];
			maxv[u]=maxv2[v];
			maxp[u]=maxp2[v];
		}else if(maxv1[u]<maxv2[v]&&maxv2[v]<maxv[u]){
			maxv2[u]=maxv1[u];
			maxp2[u]=maxp1[u];
			maxv1[u]=maxv2[v];
			maxp1[u]=maxp2[v];
		}else if(maxv2[u]<maxv2[v]&&maxv2[v]<maxv1[u]){
			maxv2[u]=maxv2[v];
			maxp2[u]=maxp2[v];
		}
		if(maxl[u]<maxl[v]){
			maxl1[u]=maxl[u];
			maxpl1[u]=maxpl[u];
			maxl[u]=maxl[v];
			maxpl[u]=maxpl[v];
		}else if(maxl1[u]<maxl[v]&&maxl[v]<maxl[u]){
			maxl1[u]=maxl[v];
			maxpl1[u]=maxpl[v];
		}
		if(maxl[u]<maxl1[v]){
			maxl1[u]=maxl[u];
			maxpl1[u]=maxpl[u];
			maxl[u]=maxl1[v];
			maxpl[u]=maxpl1[v];
		}else if(maxl1[u]<maxl1[v]&&maxl1[v]<maxl[u]){
			maxl1[u]=maxl1[v];
			maxpl1[u]=maxpl1[v];
		}
		s.insert({maxl[v],maxpl[v]});
		s.insert({maxl1[v],maxpl1[v]});
	}
	int cnt=0;
	if(a[u].b==maxv[u]){
		cnt++;
	}
	for(auto v:g[u]){
		if(maxv[u]==maxv[v]){
			cnt++;
			vis[u]|=vis[v];
		}
	}
	if(cnt>=2){
		vis[u]=1;
	}
	s.insert({a[u].l,u});
	for(auto v:g[u]){
		if(s.empty())continue;
		auto it=--s.end();
		while((*it).second==maxpl[v]||(*it).second==maxpl1[v]){
			if(it==s.begin()){
				break;
			}
			--it;
		}
		if((*it).second!=maxpl[v]&&(*it).second!=maxpl1[v]){
			ff[v]=(*it).second;
			if(s.lower_bound({(*it).first,0})==s.end()){
				continue;
			}
			if(s.lower_bound({(*it).first,0})==s.begin()){
				continue;
			}
			auto it1=--s.lower_bound({(*it).first,0});
			while((*it1).second==maxpl[v]||(*it1).second==maxpl1[v]){
				if(it1==s.begin()){
					break;
				}
				--it1;
			}
			if((*it1).second!=maxpl[v]&&(*it).second!=maxpl1[v]){
				ff1[v]=(*it1).second;
			}
		}
	}
}
void dfs1(int u){
	for(auto v:g[u]){
		if(ff[u]&&a[ff[u]].l>a[ff[v]].l){
			ff1[v]=ff[v];
			ff[v]=ff[u];
		}else if(ff[u]&&a[ff[u]].l>a[ff1[v]].l&&a[ff[u]].l<a[ff[v]].l){
			ff1[v]=ff[u];
		}
		if(ff1[u]&&a[ff1[u]].l>a[ff1[v]].l&&a[ff1[u]].l<a[ff[v]].l){
			ff1[v]=ff1[u];
		}
		dfs1(v);
	}
}
signed main(){
//	freopen("soldier.in","r",stdin);
//	freopen("soldier.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		g[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].b>>a[i].l;
	} 
	dfs(1);
	dfs1(1);
	for(int i=1;i<=q;i++){
		int s;
		cin>>s;
		if(vis[s]&&a[ff[s]].l){
			cout<<maxv[s]<<"\n";
			continue;
		}
		if(maxv1[s]){
			if(!ff[s]&&!ff1[s]){
				cout<<maxv1[s]<<"\n";
				continue;
			}
			if(ff[s]&&!ff1[s]){
				if(maxv1[s]+a[ff[s]].l==maxv[s]){
					cout<<max(maxv1[s],maxp2[s]>=1?maxv2[s]+a[ff[s]].l:-1)<<"\n";
				}else{ 
					if(maxv1[s]+a[ff[s]].l>maxv[s]){
						cout<<maxv[s]<<"\n";
					}else{
						cout<<maxv1[s]+a[ff[s]].l<<"\n";
					}
				}
				continue;
			}
			if(maxv1[s]+a[ff[s]].l==maxv[s]){
				cout<<max(maxv1[s]+a[ff1[s]].l,maxp2[s]>=1?maxv2[s]+a[ff[s]].l:-1)<<"\n";
			}else{
				if(maxv1[s]+a[ff[s]].l>maxv[s]){
					cout<<maxv[s]<<"\n";
				}else{
					cout<<maxv1[s]+a[ff[s]].l<<"\n";
				}
			}
		}else{
			if(sz[s]==1){
				cout<<"0\n";
			}else{
				if(ff[s]){
					cout<<maxv[s]<<"\n";
				}else{
					cout<<maxv1[s]<<"\n";
				}
			}
		}
	}
	return 0;
}
/*
10 1
1 2 2 2 2 3 3 7 8
1 0
4 7
4 1
7 8
7 8
7 3
5 8
5 4
7 4
3 6
2
*/

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2024-09-03 09:20:53
评测时间
2024-09-03 09:20:53
评测机
分数
75
总耗时
1246ms
峰值内存
30.887 MiB