WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #184 Div2 D 「Olya and Graph」

問題

http://codeforces.com/contest/305/problem/D

オリヤはn個の頂点とm個の辺を持つ、方向があり、重みなしのグラフを持っていた。いくつかの規則を守り、グラフの1番からn番への頂点を移動する事を考える。現在のグラフは辺を辿って、v -> uへと移動できなたらば、それはv < uとなっている。

今、オリヤは、好きなだけ辺の追加することによって(追加しなくても良い)以下のような性質を持つグラフにするのに、何通りの追加の仕方があるかを知りたい。

1. 頂点iから頂点i+1, i+2, ... nへたどり着くことが可能である。
2. 頂点vから頂点uへと到達可能であれば、v < uとなっていること。
3. 2つの頂点間では、辺の数は多くとも1つであること。
4. 頂点iから頂点jへの最短距離はj - i <= kのとき、j - iであること。
5. 頂点iから頂点jへの最短距離はj - i > kのとき、j - iもしくはj - i - kであること。

2つのグラフにおいて、ある辺を片方が持っていたがもう一方がもっていなかった場合、それは違う追加の仕方であるとみなす。

上記のルールを守る、辺の追加の仕方の数を出力せよ。

制約

1 <= n <= 10^6
1 <= m <= 10^5
1 <= k <= 10^6


Editorialsを見て

あとで


ソースコード

const int MOD = 1000000007;

int degs[1000050];
bool use[1000050];

int add( int a, int b ){
    a += b;
    if( a >= MOD ) a -= MOD;
    return a;
}

int main() {

    int n, m, k;
    scanf( "%d %d %d", &n, &m, &k );

    // degs初期化
    degs[0] = 1;
    for( int i = 1; i <= n; i++ ){
        degs[i] = add( degs[i-1], degs[i-1] );
    }

    // エッジ入力
    vector< int > edges; // edges[i] : 頂点iから頂点i+k+1へのエッジ
    memset( use, false, sizeof(use) ); // use[i] : 頂点iから頂点i+k+1への辺があるか
    for( int i = 0; i < m; i++ ){
        int u, v;
        scanf( "%d %d", &u, &v );
        // 一つ進むだけの辺
        if( v - u == 1 ) continue;
        // i->i+k+1以外に辺が付いてたらダメ
        if( v - u != k + 1 ){
            cout << 0 << endl;
            return 0;
        }
        // 辺を追加
        edges.push_back( u );
        use[u] = true;
    }
    m = edges.size();
    
    // 2回以上辺を通れてしまわないかチェック
    for( int i = 1; i < m; i++ ){
        if( !(edges[i] < edges[0] + k + 1) ){
            cout << 0 << endl;
            return 0;
        }
    }

    // 辺を置ける範囲を取得
    int start = 1;
    int end = n - k - 1;
    if( m != 0 ){
        start = max( start, edges[m-1] - k );
        end = min( end, edges[0] + k );
    }

    // 頂点を前から見ていき、答えを出す
    int ans = 0;
    int e = m; // 範囲中に含む辺の数
    for( int v = start; v <= end; v++ ){
        // この頂点は既に張られている
        if( use[v] ){
            e--; 
        }else{
            // この頂点に張ったときの場合の数を数える
            int cnt = min( end, min( n - k - 1, v + k )) - v - e;
            ans = add( ans, degs[cnt] );
        }
    }
    ans++; // まったく辺を張らない場合
    cout << ans << endl;

    return 0;
}