Codeforces Round #184 (Div. 2) D. Olya and Graph

,

誤読してしまった。最短路の長さの条件を、最短路となる道の数の条件と勘違いした。とてもつらい。

D. Olya and Graph

問題

頂点のindexがtopological sortされたDAG $G$と、整数$k$が与えられる。 $G$にいくつかの辺を加える。 以下の条件を満たすような辺の追加の仕方の数を答えよ。

  • DAGでありtopological sort済みという条件を保つ。
  • 多重辺は禁止。
  • 任意の頂点$u, v$($u \lt v$)に関して、$u$から$v$への道が存在し、その最短路の長さは$v - u$か$v - u - k$に一致する。

解法

頂点$i$から$i+1$へは必ず辺が必要なので、これを全て張る。 他に辺がないとすると、頂点$u,v$間の最短路の長さは全て$v - u$になる。

頂点$u,v$間の最短路の長さは$v - u - k$でもよいので、頂点$i$から$i+k+1$へshortcut辺を張ってもよい。 逆にこれら以外の辺がひとつでも存在すれば、条件を満たさない。

また、頂点$u,v$で、その最短路中でこのshortcutの辺を複数回使用するようなことがあれば、これは条件を満たさない。 つまりshortcut辺のsourceになっている頂点のindexを$i$とすると、shortcut辺のsourceになれる頂点は$i, i+1, \dots, i+k$のみである。

以上をもとに計算すればよい。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
constexpr ll mod = 1000000007;
ll powll(ll x, int y) {
ll z = 1;
for (int i = 0; (1 << i) <= y; ++ i) {
    if (y & (1 << i)) {
        z = (z * x) % mod;
    }
    x = (x * x) % mod;
}
return z;
}

int main() {
int n, m, k; cin >> n >> m >> k;
vector<int> u(m), v(m);
repeat (i,m) {
    cin >> u[i] >> v[i];
    -- u[i]; -- v[i];
}

bool is_valid = true;
vector<bool> has_shortcut(n);
int leftmost_shortcut = 1000000007;
int rightmost_shortcut = -1;
repeat (i,m) {
    if (v[i] - u[i] == 1) {
        // nop
    } else if (v[i] - u[i] == k+1) {
        has_shortcut[u[i]] = true;
        leftmost_shortcut  = min( leftmost_shortcut, u[i]);
        rightmost_shortcut = max(rightmost_shortcut, u[i]);
    } else {
        is_valid = false;
        break;
    }
}
if (leftmost_shortcut + k+1 <= rightmost_shortcut) {
    is_valid = false;
}
vector<int> acc_shortcut(n+1);
repeat (i,n) acc_shortcut[i+1] = acc_shortcut[i] + has_shortcut[i];

ll result = 0;
if (not is_valid) {
    // nop
} else {
    result += 1;
    repeat (i,n) {
        if (i + k+1 < n) {
            if (i <= leftmost_shortcut and rightmost_shortcut < i + k+1) {
                int j = min(k, n - (i + k+1) - 1) - (acc_shortcut[i+k+1] - acc_shortcut[i+1]);
                result = (result + powll(2, j) - has_shortcut[i]) % mod;
            }
        }
    }
}
cout << result << endl;
return 0;
}