AtCoder Beginner Contest 061

Updated:

AtCoder Beginner Contest 061

Solutions

A - Between Two Integers

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

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]$.

Tags:

Categories: