D - Find by Query

20回以下の指定なので、log時間の方法を疑います。すなわち、二分探索です。

最初、 $l = 1, r = N$ とします。最初、 $[l,r]$ は、0......1です。

$m=\lfloor \frac{r+l}{2}\rfloor$ とします。 $S_m = 0$ の場合、0...0...1という感じです。 $l\leftarrow m$ とすると、 $[l,r]$ は、0......1となります。

$S_m = 1$ の場合、0...1...1という感じです。 $r\leftarrow m$ とすると、 $[l,r]$ は、0......1となります。

このように二分探索を繰り返すと、常に $[l,r]$ は、0......1という状態が保たれます。 $r=l+1$ となるまでこれを繰り返し、 $l$ を $p$ とすれば、答えの条件を満たします。

E - Nearest Black Vertex

問題文中の条件である、

について、どの頂点を黒にすればよいか決めることは困難です。しかし、白に塗る頂点は以下のように確定します。

これにより、全ての $p_i$ について、黒に塗った頂点との距離が最小のものが $d_i$ 未満とならないことが保証されます。

白で塗った頂点以外は、何色で塗ってもよいです。そのため、条件を満たすために黒で塗るのが最適です。

これで白黒の塗り方が決まりました。後は、問題文の条件を満たすか確かめれば良いです。

塗り方の決定及び条件を満たすかの確認は全点対間最短経路が分かっていればよく、Warshall-Floyd法では間に合わないので、全頂点を始点としてBFSを行えばよいです。計算量は $O(N(N+M)+NK)$ だと思います。