列表

详情

NC232335. Join TB's Party

描述

TB is going to hold a tea party at R318 of South Tower!

The tea party is so popular that there are M students present. However, they soon discover that R318 has no chair, not a single one. Luckily, they can seek for chairs at other rooms of South Tower.


There are totally N rooms in South Tower, including R318. For convenience, R318 is labeled as room 1 among these N rooms.

These rooms are connected by exactly N - 1 corridors, where each corridor has its own length.

That is to say, all rooms form a tree rooted room 1 with weighted edges.


Now, each student is going to set off for exactly one chair and return to R318.

All students move in the same pace. It takes a student exactly L seconds to walk through an edge with length L (from one end to another end).

Room i can provide at most C_i chairs, and has a congestion value P_i .

For those rooms that possess at least 1 chair, the first student who arrives at the room can take away that first chair immediately.

However, if another student wants to take a chair from the same room, suppose the previous chair was taken away at moment x, he or she must wait until moment  or later to take his or her chair.


TB must begin the tea party as soon as possible. Please help him find the shortest time such that every student can return to R318 with a chair within time limitation. If the number of chairs in South Tower is not enough for these M students, output "Too many students!" (without quotes).


Note that a student carrying a chair moves as fast as a student that does not carry one. Each student can operate at most 1 chair in the whole process. Time used in irrelevant processes such as picking up a chair can be ignored.


输入描述

The input consists of:
    One line containing two integers N,M.
    For the next N - 1 lines, each line contains two integers C_i,P_i , denoting information about rooms except R318.
    For the next N - 1 lines, each line contains three integers u,v,l , denoting a corridor that connects room u and room v with length l.

输出描述

Output the minimum time that every student can return to R318 with a chair. The answer's unit should be second.
If chairs are not enough, output "Too many students!" (without quotes).

示例1

输入: 

3 4
3 1
1 2
3 1 2
1 2 2

输出: 

6

说明:

In sample 1, one of the optimal solution is: students A, B, and C head out for room 2 and student D heads out for room 3.

示例2

输入: 

5 6
2 5
5 2
2 1
4 2
1 2 2
5 2 1
3 1 4
4 5 3

输出: 

10

说明:

Student A, B, and C leave R318 at moment 0/0/0, arrive at room 2 at moment 2/2/2, take their own chairs at moment 2/3/4, and return to R318 at moment 4/5/6.

Student D leaves R318 at moment 0, arrives at room 3 at moment 2, takes his or her chair at moment 2, and returns to R318 at moment 4.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 1809ms, 内存消耗: 31608K, 提交时间: 2021-12-26 16:14:48 

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e5;
int  p[N],c[N];
vector< pair<int,int> >  g[N];
int dfs(int u,int fa,int d,int li){
   if (2*d>li) return 0;
   int res=0;
   if(p[u]) res=min(c[u],(li - 2 * d)/p[u] + 1);
		else res = c[u];
		for(auto &[v, w] : g[u]){
			if(v == fa) continue;
			res += dfs( v, u, d + w, li);
		}
		return res;
}
int n,m;
bool check(int x){
    return dfs(0,0,0,x)>=m;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
	cin>>n>>m;
    for (int i=1;i<n;++i) cin>>c[i]>>p[i];
    
    for(int i=1;i<n;++i){
        int u,v,w;
        cin>>u>>v>>w;--u;--v;
        g[u].emplace_back(v,w);
        g[v].emplace_back(u,w);
    }
    int l=0,r=1e18;
    while (l<r){
        int mid=(l+r)/2;
        if (check(mid)) r=mid;
         else l=mid+1;
    }
    if (l == 1e18) cout <<"Too many students!\n";
	 else cout<<l<<"\n";
	return 0;
}

上一题

© 2024 nowcoder.com