10WA
  • 板块P1113 杂务
  • 楼主MarsPlan2025
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/9 18:49
  • 上次更新2024/12/9 21:49:46
查看原帖
10WA
1080300
MarsPlan2025楼主2024/12/9 18:49
#include <bits/stdc++.h>
using namespace std;
int n,t[100005]={0},x,s[100005]={0};
vector<int> p[100005];
queue<int> q;
int a[100005]={0};
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&t[i]);
		int r;
		do{
			scanf("%d",&r);
			if(r!=0){
				p[r].push_back(i);
				s[i]++;
			}
		}while(r!=0);
	}
	for(int i=1;i<=n;i++){
		if(s[i]==0){
			q.push(i);
			a[i]=t[i];
		}
	}
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int i=0;i<p[v].size();i++){
			s[p[v][i]]--;
			a[p[v][i]]=max(a[p[v][i]],a[i]+t[p[v][i]]);
			if(s[p[v][i]]==0){
				q.push(p[v][i]);
			}
		}
	}
	int s=0;
	for(int i=1;i<=n;i++){
		s=max(s,a[i]);
	}
	printf("%d",s);
	return 0;
} 
2024/12/9 18:49
加载中...