AtCoder Beginner Contest 061


AtCoder Beginner Contest 061

Source codes


A - Between Two Integers

Determine if $A \leq C \land C \leq B$.

B - Counting Roads

Do as they indicate us to.

C - Big Array

Possess the integers by vector<int> V(100010, 0);. Then binary search works.

D - Score Attack

Assume $0$-indexed. We possess the paths by vector<Edge> V; where Edge is a struct which has the source $a$, the destination $b$ and the cost $-c$. The shortest path is determined by Bellman–Ford’s algorithm. Note that the shortest path consists at most $N - 1$ edges.

  vector<ll> D(N, infty);
  D[0] = 0;
  for (auto k = 0; k < N - 1; ++k)
    for (auto i = 0; i < M; ++i)
      ch_min(D[E[i].dst], D[E[i].src] + E[i].cost);

What we should do is to separate the shortest path part and the loop determination part. How can we determine the negative loop? In this problem, if both of the followings are satisfied, the answer is inf.

  1. There exists a negative loop connected from $0$.
  2. One of those are connected to $N - 1$.

We create vector<bool> update(N, false); and will update it.

For 1., we just execute the update once more. For 2., we execute $N - 1$ times more, too. If the condition 2. holds, updated[N - 1] will become true since the loop consists of at most $N$ edges. This enable us to distinguish inf and $D[N - 1]$.