JOISC 2023
先发篇博客防止我鸽掉。
D1T1 Two Currencies
树上主席树板子。
D1T2 Festivals in JOI Kingdom 2
不会。
D1T3 Passport
首先每个时刻到达的点构成了一个区间，那么可以到达所有点等价于可以到达 \(1\) 号点和 \(n\) 号点。由此只用考虑点和点之间的路径。我们现在已知 \(1\) 号点和 \(n\) 号点到所有点的最短路，但是这两个最短路之间可能有边被重复计入贡献。考察 \(x \rightarrow 1\) 和 \(x \rightarrow n\) 的关系。发现如果有一公共点 \(t\) 那么 \(t\) 前面的路径都是一样的。所以重复的部分一定是一个前缀。既然如此，那么我们初始令答案等于两条最短路的和，对于 \(x\) 我们考虑用所有出边来松弛，这又是一个最短路，这时候得到的答案就是正确的了。时间复杂度 \(O(n \log n)\)。连边的部分需要线段树优化。