F - Absolute Minima 概要 関数f(x)が与えられる。関数f(x)は最初f(x) = 0の定数関数である。 クエリがQ個与えられるので、それに従い操作する。クエリは下記2つ。 更新クエリ："1 a b"の形で与えられ、f(x) 求値クエリ："2" の形で与えられ、f(x)の最小値を…

F - Colorful Tree 概要 N頂点の木が与えられる。辺iは頂点ai, biを結び、色ciがついている。また辺の長さはdiである。 Q個のクエリが与えられる。クエリiではxi, yi, ui, viが与えられ、下記の問いに答えよ。 色xiの辺の長さがyiになったとき、uiからviまで…

E - 迷路 概要 N×Mのマス目が与えられる。マス目は迷路となっており、#が壁を表す。 長さKの文字列dが与えられる。この迷路はこの文字列に従って進むことが出来る。具体的には、文字列はU, D, L, Rの文字から成り、i秒後にi % K + 1文字目の命令に沿って迷路…

D - IntegerotS 概要 N項の整数列A, Bと整数Kが与えられる。数列Aiからいくつかの項を選び、それらの項すべてについてのbitwise orがK以下であるとき、対応するBiの和の最大値を求めよ。 制約 1 ≦ N ≦ 10^5 0 ≦ K 0 ≦ Ai 1 ≦ Bi ≦ 10^9 方針 Aiの全ての組み…

E - Virus Tree 2 概要 N頂点の木を下記の要領で塗り分ける。塗り分けにK色まで使えるとき、塗り分けの通り数を求めよ。(mod 10^9 + 7 して出力) 2つの異なる頂点x, yについて、xとyの間の距離が2以下ならxとyは異なる色で塗られる。 制約 1 ≦ N, K ≦ 10^5 …

C - Successive Subtraction 概要 N項の数列Aが与えられる。これらの数列が黒板に書いてある。次の操作を繰り返し行い、最終的に黒板に書いてある数字が1つになった時の数字の最大値と、その数値を与える操作を出力せよ。 黒板の数字を2つ選び、x, yとする。…

E - Hopscotch Addict 概要 有向グラフが与えられる。始点Sから終点Tまでの経路で長さ3がの倍数のもののうち最小のものについて、その長さを3で割ったものを出力せよ。（けんけんぱで移動できるか） 制約 2 ≦ N ≦ 10^5 0 ≦ M ≦ min(10^5, N * (N - 1)) 方針 …