結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー firiexpfiriexp
提出日時 2021-01-22 22:40:17
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,021 bytes
コンパイル時間 944 ms
コンパイル使用メモリ 98,872 KB
最終ジャッジ日時 2023-08-08 17:52:30
合計ジャッジ時間 6,471 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:59:48: エラー: too many initializers for ‘std::array<int, 3>’
   59 |         G[u].emplace_back(array<int, 3>{v, l, a});
      |                                                ^
main.cpp:60:49: エラー: too many initializers for ‘std::array<int, 3>’
   60 |         G2[v].emplace_back(array<int, 3>{u, l, a});
      |                                                 ^
main.cpp:70:30: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   70 |                 if(!visited[e[0]]) {
      |                              ^
main.cpp:71:30: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   71 |                     visited[e[0]] = 1;
      |                              ^
main.cpp:72:32: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   72 |                     Q.emplace(e[0]);
      |                                ^
main.cpp:88:30: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   88 |                 if(!visited[e[0]]) {
      |                              ^
main.cpp:89:30: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   89 |                     visited[e[0]] = 1;
      |                              ^
main.cpp:90:32: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
   90 |                     Q.emplace(e[0]);
      |                                ^
main.cpp:109:27: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
  109 |                     degg[e[0]]++;
      |                           ^
main.cpp:123:22: エラー: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
  123 |                 dp2[e[0]] += dp2[i]*e[2];

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

template <u32 M>
struct modint {
    u32 val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = u32(x); }
    modint(bool v) { val = ((unsigned int)(v) % M); }
    modint& operator++() { val++; if (val == M) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = M; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }
    modint& operator*=(const modint& b) { u64 z = val; z *= b.val; val = (u32)(z % M); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(M-2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;


int main() {
    int n, m;
    cin >> n >> m;
    n++;
    vector<vector<array<int, 3>>> G(n), G2(n);
    vector<int> deg(n);
    for (int i = 0; i < m; ++i) {
        int u, v, l, a;
        scanf("%d %d %d %d", &u, &v, &l, &a);
        G[u].emplace_back(array<int, 3>{v, l, a});
        G2[v].emplace_back(array<int, 3>{u, l, a});
    }
    { // 0 -> x;
        vector<int> visited(n);
        visited[0] = 1;
        queue<int> Q;
        Q.emplace(0);
        while(!Q.empty()){
            int i = Q.front(); Q.pop();
            for (auto &&e : G[i]) {
                if(!visited[e[0]]) {
                    visited[e[0]] = 1;
                    Q.emplace(e[0]);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if(!visited[i]) deg[i] = -INF<int>;
        }
    }
    { // x -> n
        vector<int> visited(n);
        visited[n-1] = 1;
        queue<int> Q;
        Q.emplace(n-1);
        while(!Q.empty()){
            int i = Q.front(); Q.pop();
            for (auto &&e : G2[i]) {
                if(!visited[e[0]]) {
                    visited[e[0]] = 1;
                    Q.emplace(e[0]);
                }
            }
        }
        if(!visited[0]){
            puts("0");
            return 0;
        }
        for (int i = 0; i < n; ++i) {
            if(!visited[i]) deg[i] = -INF<int>;
        }
    }
    vector<mint> dp(n), dp2(n);
    mint ans = 0;
    { // x -> n
        auto degg = deg;
        for (int i = 0; i < n; ++i) {
            if(degg[i] >= 0){
                for (auto &&e : G2[i]) {
                    degg[e[0]]++;
                }
            }
        }
        vector<int> Q;
        if(degg[n-1]){
            puts("INF");
            return 0;
        }
        Q.emplace_back(n-1);
        dp2[n-1] = 1;
        while(!Q.empty()){
            int i = Q.back(); Q.pop_back();
            for (auto &&e : G2[i]) {
                dp2[e[0]] += dp2[i]*e[2];
                if(!(--degg[e[0]])) Q.emplace_back(e[0]);
            }
        }
    }
    { // 0 -> x
        for (int i = 0; i < n; ++i) {
            if(deg[i] >= 0){
                for (auto &&e : G[i]) {
                    deg[e[0]]++;
                }
            }
        }
        vector<int> Q;
        if(deg[0]){
            puts("INF");
            return 0;
        }
        Q.emplace_back(0);
        dp[0] = 1;
        while(!Q.empty()){
            int i = Q.back(); Q.pop_back();
            for (auto &&e : G[i]) {
                dp[e[0]] += dp[i]*e[2];
                ans += (dp[i]*dp2[e[0]]*e[1])*e[2];
                if(!(--deg[e[0]])) Q.emplace_back(e[0]);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if(deg[i] > 0) {
            puts("INF");
            return 0;
        }
    }
    cout << ans.val << "\n";
    return 0;
}
0