ABC309CDE Solution - By LaDeX - 帖子

讨论

ABC309CDE Solution - By LaDeX

这里先将药按照停止时间升序排序，然后从后向前枚举，这样可发现总共的药是单调递增的。

排序后将从后往前做前缀和，寻找第一个大于的，则答案就是。

const LL N = 3e5 + 10;
LL n, K;
 
struct TYPE{
	LL x, t;
} A[N];
 
bool cmp(TYPE x, TYPE y){
	return x.t < y.t;
}
 
int main(){
	Fcin;
	cin >> n >> K;
	for (LL i = 1; i <= n; i ++){
		cin >> A[i].t >> A[i].x;
	}
	sort(A + 1, A + 1 + n, cmp);
	A[0].x = 1e18;
	for (LL i = n; i >= 0; i --){
		A[i].x += A[i + 1].x;
		if (A[i].x > K){
			cout << A[i].t + 1;
			break;
		}
	}
 
 
	return 0;
}

因为保证:

对于每个，连通。
对于每个，连通。
点不连通。

所以：

以点为起始点做一遍 Dijkstra，取中最远点的路径长度，记为。

则答案就为（两个最远点连边）。

LL n1, n2, m;
vector<LL> G[N];
 
LL Dis[N], vis[N];
void Dijkstra1(){
	queue<pair<LL, LL> > q;
	q.push(mkp(0, 1));
	Dis[1] = 0;
	while (!q.empty()){
		LL x = q.front().second; q.pop();
		if (vis[x])
			continue;
		vis[x] = 1;
		for (auto v : G[x]){
			if (Dis[v] > Dis[x] + 1){
				Dis[v] = Dis[x] + 1;
				q.push(mkp(Dis[v], v));
			}
		}
	}
	return ;
}
 
void Dijkstra2(){
	queue<pair<LL, LL> > q;
	q.push(mkp(0, n1 + n2));
	Dis[n1 + n2] = 0;
	while (!q.empty()){
		LL x = q.front().second; q.pop();
		if (vis[x])
			continue;
		vis[x] = 1;
		for (auto v : G[x]){
			if (Dis[v] > Dis[x] + 1){
				Dis[v] = Dis[x] + 1;
				q.push(mkp(Dis[v], v));
			}
		}
	}
	return ;
}
 
int main(){
	Fcin;
	memset(Dis, 0x3f, sizeof (Dis));
	cin >> n1 >> n2 >> m;
	LL u, v;
	for (LL i = 1; i <= m; i ++){
		cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
 
	Dijkstra1(); Dijkstra2();
	LL Max = 0, Ans = 1;
	Dis[0] = 0;
	for (LL i = 1; i <= n1; i ++)
		if (Dis[i] > Dis[Max])
			Max = i;
	Ans += Dis[Max];
	Max = 0;
	for (LL i = n1 + 1; i <= n1 + n2; i ++)
		if (Dis[i] > Dis[Max])
			Max = i;
	Ans += Dis[Max];
	cout << Ans;
	return 0;
}

将家族看做一颗树。

将第人投的保险的值记作（若此人没投过保险则为），它的父亲记作，从它所在的这层算起，下面还可继承保险的层数记为。

则，若投了保险，则（加一是因为并没有算上自己，只算了子孙)。

则答案就为数组中非零的数值个数。

const LL N = 3e5 + 10;
LL n, m, tree[N];
vector<LL> G[N];
bool has[N];

void DFS(LL x){
	if (tree[x] != 0)
		has[x] = 1;
	for (auto v : G[x]){
		tree[v] = max(tree[v], tree[x] - 1);
		DFS(v);
	}
	return ;
}

int main(){
	Fcin;
	cin >> n >> m;
	LL x, y;
	for (LL i = 2; i <= n; i ++){
		cin >> x;
		G[x].emplace_back(i);
	}
	for (LL i = 1; i <= m; i ++){
		cin >> x >> y;
		tree[x] = max(tree[x], y + 1);
	}
	DFS(1);
	LL Ans = 0;
	for (LL i = 1; i <= n; i ++){
		if (has[i])
			++ Ans;
	}
	cout << Ans;
	return 0;
}