{"problem":{"name":"D. Kapuluan ng Kalayaan 2","description":{"content":"Since the citizens of the country were not fussing about worrying how not to get arrested during quarantine, or hosting birthday mañanitas for their beloved police chief, the Philippines was able to f","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10268D"},"statements":[{"statement_type":"Markdown","content":"Since the citizens of the country were not fussing about worrying how not to get arrested during quarantine, or hosting birthday mañanitas for their beloved police chief, the Philippines was able to finally rightfully claim the Spratly Islands as part of their territory, and even establish a successful system of ferries connecting the islands together, with tours! Do you remember how fulfilling it was to meticulously and lovingly craft optimal solutions to these problems, after you were put in charge of the project?\n\nOf course, ever since you handed over leadership of the ferry project to another administration, the new management proceeded to thoughtlessly add more ferry routes and ruin the system you developed. But hey, you don't care about that, right? It doesn't matter that all your hard work was ruined by a new team that doesn't care about the project nearly as much as you did. Nope!\n\nTo recap, there are $n$ islands labeled $1$ to $n$, and $m$ ferry services that allow travel between pairs of islands. The $i$th ferry service connects islands $u_i$ and $v_i$, and due to the event-that-shall-not-be-named, citizens are only permitted to use this ferry if they are at least $d_i$ seconds old (because everyone knows their age down to the second, obviously). A ferry always connects two different islands, but the same pair of islands may have multiple ferry services between them. \n\nEven though the ferry services are up and running again, people are generally discouraged from leaving their houses and returning to their home province (again, due to the event-that-shall-not-be-named). Despite this, some people still insist on leaving their islands anyway! You are aware of $k$ different rebellious souls, as well as each of their respective romantic partners (there are $k$ romantic partners in total). You also know the ages of the rebels—the $i$th rebel is $H_i$ seconds old.\n\nHow do we prevent them from visiting their romantic partners? Your master plan is simple!\n\nYou will build $2 k$ houses on the islands, and relocate each of the rebels or romantic partners to these houses (one to each house), such that it is impossible for each rebel to ever reach the island of their partner by using the ferry system. The romantic partners can be assumed to stay in their assigned island and will never attempt to move. It is okay for multiple rebels or multiple partners to live on the same island, and it is even okay for a rebel to live on the same island as the partner of a different rebel, so long as it is impossible for them to reach their own partner.\n\nHow many ways can you choose where to build each of the $2 k$ houses such that this condition is fulfilled? Two ways are different if one of the rebels or one of the partners has their home on a different island between the two ways. Since this can be quite large, output your answer modulo $10^9 + 7$.\n\nThe first line of input contains three space-separated integers, $n$, $m$, and $k$, respectively.\n\nThis is followed by $m$ lines, each containing three space-separated integers $u_i$, $v_i$, and $d_i$, meaning that there exists a ferry service connecting islands $u_i$ and $v_i$ that you have to be $d_i$ seconds old in order to use.\n\nFinally, this is followed by a single line containing $k$ space-separated integers, where the $i$th of these integers is $H_i$. \n\nOutput a single line containing the answer modulo $10^9 + 7$.\n\n*For all subtasks*\n\n$2 <= n <= 10^6$\n\n$1 <= m, k <= 2 dot.op 10^5$\n\n$1 <= u_i, v_i <= n$\n\n$u_i eq.not v_i$\n\n$1 <= d_i, H_i <= 2 dot.op 10^9$\n\n*Subtask 1* (10 points):\n\n$n, m, k <= 20$\n\n*Subtask 2* (20 points):\n\n$n, m, k <= 200$\n\n*Subtask 3* (10 points):\n\n$k = 1$\n\n$n <= 7641$\n\n*Subtask 4* (15 points):\n\n$k = 1$\n\n*Subtask 5* (5 points):\n\n$d_i$ is the same across all ferry services.\n\n$n <= 7641$\n\n*Subtask 6* (10 points):\n\n$d_i$ is the same across all ferry services.\n\n*Subtask 7* (30 points):\n\nNo further constraints.\n\n## Input\n\nThe first line of input contains three space-separated integers, $n$, $m$, and $k$, respectively.This is followed by $m$ lines, each containing three space-separated integers $u_i$, $v_i$, and $d_i$, meaning that there exists a ferry service connecting islands $u_i$ and $v_i$ that you have to be $d_i$ seconds old in order to use.Finally, this is followed by a single line containing $k$ space-separated integers, where the $i$th of these integers is $H_i$. \n\n## Output\n\nOutput a single line containing the answer modulo $10^9 + 7$.\n\n[samples]\n\n## Scoring\n\n*For all subtasks*$2 <= n <= 10^6$$1 <= m, k <= 2 dot.op 10^5$$1 <= u_i, v_i <= n$$u_i eq.not v_i$$1 <= d_i, H_i <= 2 dot.op 10^9$*Subtask 1* (10 points):$n, m, k <= 20$*Subtask 2* (20 points):$n, m, k <= 200$*Subtask 3* (10 points):$k = 1$$n <= 7641$*Subtask 4* (15 points):$k = 1$*Subtask 5* (5 points):$d_i$ is the same across all ferry services.$n <= 7641$*Subtask 6* (10 points):$d_i$ is the same across all ferry services.*Subtask 7* (30 points):No further constraints.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $, $ B = (b_1, b_2, \\dots, b_m) \\in \\mathbb{Z}^m $ be finite sequences of positive integers.  \nDefine the infinite periodic extensions:  \n- $ A_i = a_{(i-1) \\bmod n + 1} $ for all $ i \\geq 1 $,  \n- $ B_i = b_{(i-1) \\bmod m + 1} $ for all $ i \\geq 1 $.  \n\nLet $ x, y \\in \\mathbb{Z} $ be autotuning offsets such that $ a_i + x \\geq 1 $ and $ b_j + y \\geq 1 $ for all $ i, j $.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 30 $  \n2. $ 1 \\leq n, m \\leq 60000 $  \n3. $ 1 \\leq q \\leq 3 $  \n4. $ 1 \\leq s_i \\leq t_i \\leq 10^{12} $  \n5. $ 1 \\leq a_k, b_k \\leq 10^6 $  \n6. $ a_i + x \\geq 1 $, $ b_j + y \\geq 1 $ for all $ i, j $  \n\n**Objective**  \nFor each query $ (s_i, t_i) $, compute:  \n$$\n\\min_{x,y \\in \\mathbb{Z}} \\sum_{k=s_i}^{t_i} \\left| (a_{(k-1) \\bmod n + 1} + x) - (b_{(k-1) \\bmod m + 1} + y) \\right|\n$$  \nsubject to $ a_j + x \\geq 1 $, $ b_\\ell + y \\geq 1 $ for all $ j, \\ell $.  \n\nLet $ d_k = a_{(k-1) \\bmod n + 1} - b_{(k-1) \\bmod m + 1} $. Then the objective becomes:  \n$$\n\\min_{x,y \\in \\mathbb{Z}} \\sum_{k=s_i}^{t_i} \\left| d_k + (x - y) \\right| \\quad \\text{with} \\quad a_j + x \\geq 1, \\; b_\\ell + y \\geq 1.\n$$  \n\nLet $ z = x - y $. Then minimize $ \\sum_{k=s_i}^{t_i} |d_k + z| $ over $ z \\in \\mathbb{Z} $, under the constraints:  \n- $ x = z + y \\Rightarrow a_j + z + y \\geq 1 \\Rightarrow y \\geq 1 - a_j - z $,  \n- $ y \\geq 1 - b_\\ell $,  \nso $ y \\geq \\max\\left( \\max_\\ell (1 - b_\\ell), \\max_j (1 - a_j - z) \\right) $.  \n\nSince $ y $ can be chosen freely to satisfy these as long as $ z $ is fixed, the binding constraint reduces to:  \nThere exists $ y \\in \\mathbb{Z} $ such that $ y \\geq \\max(1 - \\min_j a_j - z, 1 - \\min_\\ell b_\\ell) $.  \nThis is always satisfiable for any integer $ z $, because $ y $ can be chosen large enough.  \n\nThus, the constraint is **always feasible** for some integer $ y $, given any integer $ z $.  \n\nTherefore, the problem reduces to:  \nFor each query $ (s, t) $, compute:  \n$$\n\\min_{z \\in \\mathbb{Z}} \\sum_{k=s}^{t} |d_k + z|\n$$  \nwhere $ d_k = a_{(k-1) \\bmod n + 1} - b_{(k-1) \\bmod m + 1} $.  \n\nLet $ D = (d_s, d_{s+1}, \\dots, d_t) $. The sum $ \\sum |d_k + z| $ is minimized when $ z $ is the **median** of $ -D $.  \nEquivalently, minimize over $ z \\in \\mathbb{Z} $:  \n$$\n\\sum_{k=s}^{t} |z - (-d_k)|\n$$  \nwhich is minimized when $ z $ is the median of the multiset $ \\{-d_k \\mid k = s, \\dots, t\\} $.  \n\nThus, the minimal beat drop level is the sum of absolute deviations from the median of $ \\{-d_k\\}_{k=s}^t $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10268D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}