問題一覧 > 通常問題

No.468 Useful Competitive Programming: Practical Edition

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 74
作問者 : kuuso1 / テスター : tubo28
お気に入りにしたユーザー ProblemId : 1456 / 自分の提出
問題文最終更新日: 2026-06-25 10:34:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

Note

This problem was created as the article for day 18 of Advent Calendar Contest Advent Calendar 2016.

Background

A well-known set of quality control techniques is called the "New Seven QC Tools".
This time, let us take a close look at one of them, the "arrow diagram method".
The "arrow diagram method" is a technique that represents the man-hours and the ordering relations of the tasks needed to accomplish a project,
as a diagram like the one below, in order to find bottlenecks and to manage progress efficiently.


As in the figure above, the connections in the whole project are drawn using "nodes" and "tasks", and each task is labeled with the time it requires.
A node represents an individual effort within the project, or a checkpoint such as a milestone.
To start tasks from a node, all tasks leading to that node must be completed.
For example, if you want to synchronize the completion times of one effort and another, you draw an arrow with task time $0$.
(like the one from node $4$ to node $5$ in the figure)
If this project starts at time $0$, the time required for completion can be found, for example, as shown in the figure below.



By finding, for each node, the earliest time at which work can start (the earliest node time), you can calculate the time required overall,
and you can also find, for each node, the latest time by which work must start in order not to delay the whole project (the latest node time).
If the latest node time and the earliest node time coincide, work must start as soon as it becomes possible to start,
which means that this node is rate-limiting for the whole project.
By connecting such nodes, you can identify the process that is the bottleneck of the whole project (the critical path).


Problem Statement


Now, you are the leader of a project with a cumulative total of $N$ people.
These $N$ people are named $0, 1, \dots, (N-1)$. $0$ and $(N-1)$ are you, and you declare the start and the end of the project.
The project has a total of $M$ tasks.
The $i$-th task $(0 \le i < M)$ is assigned to $A_i$, takes time $C_i$ to complete, and is then passed on to the next person, $B_i$.
Every member $(0, 1, \dots, (N-1))$ can start their own tasks only after all tasks coming to them have been completed,
but you may assume that the tasks a member holds can all proceed completely in parallel.
(If a member starts at time $t$, the $k$ tasks assigned to that member (with required times $\{ C_0,C_1,C_2,\dots , C_{k-1}\}$)
 are completed at times $\{ t + C_0, t + C_1, t + C_2, \dots , t + C_{k-1} \}$, respectively.)

Report the following information, which the higher-ups surely want to know, in the specified format.
・The minimum time required to complete the whole project
・The proportion of the cumulative personnel that can be expected to have slack while achieving completion in the minimum time (the cumulative personnel not on a critical path)

Input

$N$ $M$
$A_0$ $B_0$ $C_0$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_{M-1}$ $B_{M-1}$ $C_{M-1}$


All inputs are integers and satisfy the following constraints.
$3\le N \le 10^5$
$2\le M \le 5 \times 10^5$
$0 \le A_i < N$ , $0 \le i < (M-1)$
$0 \le B_i < N$ , $0 \le i < (M-1)$
$0 \le C_i < 160$ , $0 \le i < (M-1)$
It is guaranteed that the whole is connected, and that $0$ is the project start and $N-1$ is the completion.
Also, no loops of tasks occur.

Output

$T$ $P/N$

Here, $T$ is the minimum time required to complete the whole project.
$P$ is the number of cumulative personnel that can be expected to have slack while achieving completion in the minimum time (the cumulative personnel not on a critical path).
For $N$, output the given $N$ as is.
Print a newline at the end.

Sample

Sample 1
Input
8 12
0 1 3
1 2 7
1 3 2
2 4 1
3 4 6
2 6 4
3 5 1
4 6 2
4 5 0
4 7 4
6 7 2
5 7 4
Output
16 3/8

This is the case shown in the figure above. The $3$ people are the $3$ members $3,4,5$.

Sample 2
Input
5 4
0 3 3
3 1 2
1 2 3
2 4 1
Output
9 0/5


This is the case shown here.
Note that the start and the completion are guaranteed to be $0$,$N-1$ respectively, but $A_i < B_i$ is not guaranteed for each task.

Sample 3
Input
8 12
0 1 3
0 2 3
1 3 3
1 4 3
2 3 3
2 4 3
3 5 3
3 6 3
4 5 3
4 6 3
5 7 3
6 7 3
Output
12 0/8


Of course, even when things appear to proceed in parallel, it is possible that everyone is on a critical path.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。