/ Randle /

记录详情

Runtime Error

/in/foo.cc: In function 'void build(int, int, int)':
/in/foo.cc:91:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
# 状态 耗时 内存占用
#1 Accepted 70ms 84.59 MiB
#2 Accepted 70ms 84.586 MiB
#3 Accepted 59ms 84.582 MiB
#4 Accepted 59ms 84.488 MiB
#5 Accepted 58ms 84.586 MiB
#6 Accepted 58ms 84.52 MiB
#7 Accepted 67ms 85.586 MiB
#8 Accepted 178ms 94.648 MiB
#9 Accepted 62ms 85.281 MiB
#10 Accepted 81ms 90.156 MiB
#11 Accepted 105ms 95.113 MiB
#12 Accepted 122ms 98.52 MiB
#13 Accepted 90ms 91.805 MiB
#14 Accepted 127ms 98.734 MiB
#15 Runtime Error 101ms 100.477 MiB
#16 Runtime Error 114ms 102.578 MiB
#17 Accepted 189ms 98.312 MiB
#18 Accepted 190ms 96.855 MiB
#19 Accepted 191ms 96.57 MiB
#20 Accepted 190ms 100.707 MiB

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int maxn=1e6+10;
int b[maxn],c[maxn];
int n,q;
int fa[maxn];
vector<int>v[maxn];
int dfn[maxn];
int cnt;
int mp[maxn];
struct Tree{
	int l,r;
	pair<int,int>maxx;
}tree[4*maxn];
int maxx[maxn],maxx2[maxn],maxx3[maxn];
int sz[maxn];

void dfs(int id)
{
	dfn[id]=++cnt;
	mp[cnt]=id;
	maxx[id]=b[id];
	sz[id]=1;
	for(int i:v[id])
	{
		dfs(i);
		sz[id]+=sz[i];
		if(maxx[i]>maxx[id])
		{
			if(maxx[id]!=maxx2[id])
			{
				maxx3[id]=maxx2[id];
			}
			maxx2[id]=maxx[id];
			maxx[id]=maxx[i];
		}
		else if(maxx[i]>maxx2[id])
		{
			maxx3[id]=maxx2[id];
			maxx2[id]=maxx[i];
		}
		else if(maxx[i]>maxx3[id]&&maxx[i]!=maxx2[id])
		{
			maxx3[id]=maxx[i];
		}
		if(maxx2[i]>maxx2[id])
		{
			maxx3[id]=maxx2[id];
			maxx2[id]=maxx2[i];
		}
		else if(maxx2[i]>maxx3[id]&&maxx2[i]!=maxx2[id])
		{
			maxx3[id]=maxx2[i];
		}
		if(maxx3[i]>maxx3[id]&&maxx3[i]!=maxx2[id])
		{
			maxx3[id]=maxx3[i];
		}
	}
}

pair<int,int>merge(pair<int,int>_a,pair<int,int>_b)
{
	if(_b.first>_a.first)
	{
		_a.second=_a.first;
		_a.first=_b.first;
	}
	else if(_b.first>_a.second&&_b.first!=_a.first)
	{
		_a.second=_b.first;
	}
	if(_b.second>_a.second&&_b.second!=_a.first)
	{
		_a.second=_b.second;
	}
	return _a;
}

void build(int id,int l,int r)
{
	tree[id].l=l;
	tree[id].r=r;
	if(l==r)
	{
		tree[id].maxx.first=c[mp[l]];
		return;
	}
	int mid=l+r>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tree[id].maxx=merge(tree[id*2].maxx,tree[id*2+1].maxx);
}

pair<int,int>ask(int id,int l,int r)
{
	if(l>r||tree[id].r<l||tree[id].l>r)
	{
		return {0,0};
	}
	if(tree[id].l>=l&&tree[id].r<=r)
	{
		return tree[id].maxx;
	}
	return merge(ask(id*2,l,r),ask(id*2+1,l,r));
}

signed main()
{
//	freopen("soldier15.in","r",stdin);
//	freopen("soldier15.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i];
		v[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i]>>c[i];
	}
	dfs(1);
	build(1,1,n);
	while(q--)
	{
		int s;
		cin>>s;
		if(sz[s]==1)
		{
			cout<<"0\n";
			continue;
		}
		pair<int,int>maxxx=merge(ask(1,1,dfn[s]-1),ask(1,dfn[s]+sz[s],n));
		if(maxx3[s]==0)
		{
			if(maxxx.first==0)
			{
				cout<<maxx2[s]%maxx[s]<<endl;
			}
			else if(maxx[s]==maxx2[s]+maxxx.first)
			{
				cout<<max(maxx2[s],maxx2[s]+maxxx.second)<<endl;
			}
			else if(maxx[s]>maxx2[s]+maxxx.first)
			{
				cout<<maxx2[s]+maxxx.first<<endl;
			}
			else if(maxx[s]<maxx2[s]+maxxx.first)
			{
				cout<<maxx[s]<<endl;
			}
			continue;
		}
		if(maxxx.first==0)
		{
			if(maxx[s]==maxx2[s])
			{
				cout<<maxx3[s]<<endl;
			}
			else
			{
				cout<<maxx2[s]<<endl;
			}
			continue;
		}
		if(maxx[s]==maxx2[s]+maxxx.first)
		{
			cout<<max(max(maxx2[s],maxx2[s]+maxxx.second),maxx3[s]+maxxx.first)<<endl;
		}
		else if(maxx[s]>maxx2[s]+maxxx.first)
		{
			cout<<maxx2[s]+maxxx.first<<endl;
		}
		else if(maxx[s]<maxx2[s]+maxxx.first)
		{
			cout<<maxx[s]<<endl;
		}
	}
	return 0;
}
/*
in:
10 3
1
2
3
2
4
6
5
1
4
6 6
4 2
10 6
7 1
1 6
2 2
9 7
5 3
9 6
9 7
3
6
4
out:
10
8
9
*/

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2024-09-02 16:07:00
评测时间
2024-09-02 16:07:00
评测机
分数
90
总耗时
2190ms
峰值内存
102.578 MiB