CS Academy Round #83 - Firestarter

• 問題
• AC

着火クエリ$(T_i, A_i, B_i, X_i)$に対して新しい頂点$V_i$を導入し、辺$\{A_i, B_i\}$を分割して長さ$X_i$の辺$\{A_i, V_i\}$と長さ$L-X_i$の辺$\{V_i, B_i\}$を張る。ひとつの辺上に複数の着火が起こる場合には、3つ以上に分割する。こうしてできたグラフ上で、各頂点に初めて火が到達する時間を求める。具体的には、$V_i$の距離を$d[V_i] := T_i$とセットして多点スタートのダイクストラをする。（形式的には、大頂点$S$を導入して各$V_i$と$S$の間に長さ$T_i$の辺があると考えるのがよさそう。）

こうすると、頂点$v$に初めて火が到達する時間が$d[v]$に入ることになる。ただ、欲しいのはすべての辺が燃えきる時間なので、$\max d[v]$は答えにならない。長さ$l$の辺$\{u, v\}$が燃えきる時刻を$t$とすると$(t-d[u])+(t-d[v]) = l$なので、$t = (l + d[u]+d[v])/2$と求まる。この最大値を答えとすればよい。

---

時刻を決め打って二分探索をやってしまって、さすがにTLEだった。