| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14377 | 2024_DS_Summer_Lab18_Spreadsheet |
|
Description
Spreadsheet Formula Dependency
You have a spreadsheet where some cells contain formulas. A cell without a formula has an initial value of $0$. For example, cell B4 has the formula C8 + 763, and cell B5 has a value of 0.
However, some cells might have buggy formulas. The formula of several cells might depend on each other, resulting in a reference error. For example, if cell A1 has the formula B1 + 2, cell B1 has the formula C1 + 2, and cell C1 has the formula A1 + 2, then the spreadsheet reports a reference error.
If a cell has a formula that depends on a cell with a reference error, it also encounters a reference error. For example, if cell C1 has a reference error and cell C4 has the formula C1 + 2, then C4 will also have a reference error.
Given a spreadsheet, please output the results of all cells.
Input
Spreadsheet Formula Input
The first line contains two integers N and M: the number of cells in the spreadsheet and the number of cells with formulas.
The cells are labeled with 1, 2, ..., N (instead of the usual way we see in spreadsheet applications).
The following M lines describe the formula, and each line is in one of the following formats:
A x1 y- Cell x1 has a value yB x1 x2 y- Cell x1 has the formula: cell x2 + value yC x1 x2 x3 y- Cell x1 has the formula: cell x2 + cell x3 + value yD x1 x2 x3 x4 y- Cell x1 has the formula: cell x2 + cell x3 + cell x4 + value y
Constraints:
- 1 ≤ M ≤ N ≤ 105
- 1 ≤ x1, x2, x3, x4 ≤ N, 1 ≤ y ≤ 106 for all formulas
- x1 for all formulas are distinct
- The result for each cell without reference error does not exceed 1018
Output
For each cell please output "#REF!" if it has reference error, otherwise output its value.
Explanation of Sample IO
The formula and result of each cell are listed below:
| Cell ID | Formula | Result |
|---|---|---|
| 1 | 10 | 10 |
| 2 | cell 1 + 20 | 30 |
| 3 | cell 2 + 30 | 60 |
| 4 | cell 6 + 2 | reference error |
| 5 | cell 4 + 2 | reference error |
| 6 | cell 5 + 2 | reference error |
| 7 | cell 1 + cell 2 + 2 | 42 |
| 8 | cell 7 + cell 6 + 3 | reference error |
| 9 | cell 1 + cell 2 + cell 10 + 8 | 48 |
| 10 | (empty cell) | 0 |