P6381 "MdOI R2" Odyssey

Beyond the limit of supersonic speed, yet not as magnificent and ever-changing as the aurora. Faint pulses carve out a world that was once pure chaos. A deep blue flickers slowly, and epic red welcomes the peak. At the end of the blood-red sunset lie the stars of the coming night. Even the star-filled midnight sky can be covered by smoke from hell. The blazing red purgatory fades away; only golden ruins last forever. What awaits everyone here is a hard yet brilliant journey.

If positive integers $a$ and $b$ satisfy: - The product of $a$ and $b$ is the $k$-th power of a positive integer, that is, there exists a positive integer $c$ such that $ab=c^k$. Then we call $(a,b)$ a pair of **perfect numbers**. --- There is a **directed acyclic graph** with $n$ nodes and $m$ edges. Each edge in this graph has two attributes: a weight and a length. If a path $P$ satisfies **one of the following conditions**, then it is called a **perfect path**: - $P$ contains only one edge. - Starting from its beginning, $P$ consists of $p\ (p\ge 2)$ edges $e_1, e_2, e_3, \ldots e_p$. For any $1\leq i\leq p-1$, the weights of $e_i$ and $e_{i+1}$ form a perfect-number pair. You need to find the length of the longest perfect path in the graph. The length of a path is defined as the sum of the lengths of all edges on the path.

The first line contains three integers $n,m,k$, representing the number of nodes, the number of edges, and the parameter of perfect-number pairs. The next $m$ lines each contain four integers $u,v,w,l$, meaning there is a directed edge from $u$ to $v$ with weight $w$ and length $l$.

The first line contains one integer $ans$, representing the length of the longest perfect path.

【Help and Hints】 To make it easier for contestants to test their code, this problem additionally provides two extra sample tests. [Sample Input 1](https://www.luogu.com.cn/paste/wx1lz6m2) [Sample Output 1](https://www.luogu.com.cn/paste/28xe7f0x) [Sample Input 2](https://www.luogu.com.cn/paste/efgwngs5) [Sample Output 2](https://www.luogu.com.cn/paste/5hcpoayt) ---- 【Sample Explanation】 The directed acyclic graph in the sample is shown in the figure, where the red numbers on edges are the weights, and the black numbers are the lengths:  The longest perfect path is $2\to 5\to 3$, because the weights $2$ and $18$ of these two edges satisfy $2\times 18=6^2$, which is a perfect-number pair. The path length is $5+9=14$. In addition, $2\to 1\to 4\to 3,\ \ 2\to 4\to 3,\ \ 1\to 5\to 3$ and so on are also perfect paths, but they are not the longest. In the graph, the path $2\to 1\to 5\to 3$ has length $15$, which is longer, but it is not a perfect path, because the product of the first two edge weights $24$ and $8$ is $192$, which is not a square of a positive integer. That is, $(24,8)$ is not a perfect-number pair. --- 【Constraints】 **This problem uses bundled tests.** For $100\%$ of the testdata: $1\leq n\leq 10^5,\ \ 1\leq m\leq 2\times 10^5,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^5,\ \ 1\leq l\leq 10^4$. The given graph is **not guaranteed to be weakly connected**. There **may** be multiple edges from one node to another, but it is guaranteed that the given graph is a directed acyclic graph. | Subtask ID | $n\leq$ | $m\leq$ | $w\leq$ | $k\leq$ | Special Property | Score | | :--------: | :-----: | :--------------: | :-----: | :-----: | :--------------: | :---: | | Subtask 1 | $10^5$ | $2\times 10^5$ | $10^5$ | $1$ | None | $18$ | | Subtask 2 | $10$ | $10$ | $100$ | $2$ | None | $12$ | | Subtask 3 | $600$ | $1.5\times 10^3$ | $10^3$ | $2$ | None | $10$ | | Subtask 4 | $10^5$ | $2\times 10^5$ | $10^5$ | $2$ | $w$ is prime | $15$ | | Subtask 5 | $10^5$ | $2\times 10^5$ | $10^5$ | $2$ | None | $15$ | | Subtask 6 | $600$ | $1.5\times 10^3$ | $10^3$ | $5$ | None | $10$ | | Subtask 7 | $10^5$ | $2\times 10^5$ | $10^5$ | $10$ | None | $20$ | Translated by ChatGPT 5