結果
| 問題 |
No.1364 [Renaming] Road to Cherry from Zelkova
|
| コンテスト | |
| ユーザー |
 firiexp
|
| 提出日時 | 2021-01-22 22:40:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,021 bytes |
| コンパイル時間 | 793 ms |
| コンパイル使用メモリ | 98,792 KB |
| 最終ジャッジ日時 | 2025-01-18 04:55:02 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:59:48: error: too many initializers for ‘std::array<int, 3>’
59 | G[u].emplace_back(array<int, 3>{v, l, a});
| ^
main.cpp:60:49: error: too many initializers for ‘std::array<int, 3>’
60 | G2[v].emplace_back(array<int, 3>{u, l, a});
| ^
main.cpp:70:30: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
70 | if(!visited[e[0]]) {
| ^
main.cpp:71:30: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
71 | visited[e[0]] = 1;
| ^
main.cpp:72:32: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
72 | Q.emplace(e[0]);
| ^
main.cpp:88:30: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
88 | if(!visited[e[0]]) {
| ^
main.cpp:89:30: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
89 | visited[e[0]] = 1;
| ^
main.cpp:90:32: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
90 | Q.emplace(e[0]);
| ^
main.cpp:109:27: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
109 | degg[e[0]]++;
| ^
main.cpp:123:22: error: no match for ‘operator[]’ (operand types are ‘std::array<int, 3>’ and ‘int’)
123 | dp2[e[0]] += dp2[i]*e[2];
| ^
main.cpp:
ソースコード
#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;
}