結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | Chanyuh |
提出日時 | 2021-01-23 00:08:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,500 ms |
コード長 | 4,726 bytes |
コンパイル時間 | 1,818 ms |
コンパイル使用メモリ | 141,360 KB |
実行使用メモリ | 23,544 KB |
最終ジャッジ日時 | 2023-08-28 12:12:11 |
合計ジャッジ時間 | 7,201 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,004 KB |
testcase_01 | AC | 3 ms
5,236 KB |
testcase_02 | AC | 3 ms
5,000 KB |
testcase_03 | AC | 3 ms
4,956 KB |
testcase_04 | AC | 3 ms
5,008 KB |
testcase_05 | AC | 3 ms
4,948 KB |
testcase_06 | AC | 3 ms
5,164 KB |
testcase_07 | AC | 3 ms
5,008 KB |
testcase_08 | AC | 7 ms
5,612 KB |
testcase_09 | AC | 5 ms
5,232 KB |
testcase_10 | AC | 9 ms
5,644 KB |
testcase_11 | AC | 7 ms
5,364 KB |
testcase_12 | AC | 8 ms
5,760 KB |
testcase_13 | AC | 89 ms
14,192 KB |
testcase_14 | AC | 108 ms
14,680 KB |
testcase_15 | AC | 107 ms
15,572 KB |
testcase_16 | AC | 77 ms
12,336 KB |
testcase_17 | AC | 41 ms
10,956 KB |
testcase_18 | AC | 136 ms
17,956 KB |
testcase_19 | AC | 141 ms
18,044 KB |
testcase_20 | AC | 146 ms
18,180 KB |
testcase_21 | AC | 138 ms
18,032 KB |
testcase_22 | AC | 140 ms
18,168 KB |
testcase_23 | AC | 31 ms
8,600 KB |
testcase_24 | AC | 28 ms
6,708 KB |
testcase_25 | AC | 81 ms
12,680 KB |
testcase_26 | AC | 124 ms
16,436 KB |
testcase_27 | AC | 85 ms
12,304 KB |
testcase_28 | AC | 58 ms
10,608 KB |
testcase_29 | AC | 84 ms
11,692 KB |
testcase_30 | AC | 66 ms
10,596 KB |
testcase_31 | AC | 49 ms
9,420 KB |
testcase_32 | AC | 66 ms
10,492 KB |
testcase_33 | AC | 123 ms
14,920 KB |
testcase_34 | AC | 130 ms
15,552 KB |
testcase_35 | AC | 106 ms
16,200 KB |
testcase_36 | AC | 98 ms
14,748 KB |
testcase_37 | AC | 62 ms
9,532 KB |
testcase_38 | AC | 80 ms
11,224 KB |
testcase_39 | AC | 80 ms
11,044 KB |
testcase_40 | AC | 79 ms
11,028 KB |
testcase_41 | AC | 80 ms
11,004 KB |
testcase_42 | AC | 81 ms
11,076 KB |
testcase_43 | AC | 60 ms
23,544 KB |
testcase_44 | AC | 38 ms
13,592 KB |
testcase_45 | AC | 60 ms
23,544 KB |
testcase_46 | AC | 6 ms
9,456 KB |
testcase_47 | AC | 3 ms
5,228 KB |
ソースコード
#include<iostream> #include<array> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<tuple> #include<cassert> using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair<int, int> P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define Per(i,sta,n) for(int i=n-1;i>=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;} template<int mod> struct ModInt { long long x; static constexpr int MOD = mod; ModInt() : x(0) {} ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} explicit operator int() const {return x;} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator%(const ModInt &p) const { return ModInt(0); } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const{ int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } ModInt power(long long n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } ModInt power(const ModInt p) const{ return ((ModInt)x).power(p.x); } friend ostream &operator<<(ostream &os, const ModInt<mod> &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt<mod> &a) { long long x; is >> x; a = ModInt<mod>(x); return (is); } }; using modint = ModInt<mod>; int n,m; struct edge{ int to,l,a; edge(){} edge(int to,int l,int a):to(to),l(l),a(a){} }; bool visited[100010],finish[100010],roop=false; modint dp1[100010],dp2[100010]; vector<vector<edge>> G,rG; vector<bool> R1,R2; void dfs1(int s,vector<vector<edge>> &G,vector<bool> &R){ R[s]=true; for(edge e:G[s]){ if(R[e.to]) continue; dfs1(e.to,G,R); } } // vector<int> topological_sort(int n,vector<vector<int>> &G){ // vector<int> deg(n,0); // rep(i,n){ // for(int t:G[i]){ // } // } // } void calc(int s){ visited[s]=true; for(edge e:rG[s]){ if(!R1[e.to] || !R2[e.to]) continue; if(visited[e.to] && !finish[e.to]){ roop=true; continue; } if(!visited[e.to]) calc(e.to); dp1[s]+=dp1[e.to]*e.a+dp2[e.to]*e.a*e.l; dp2[s]+=dp2[e.to]*e.a; } finish[s]=true; } void solve(){ cin >> n >> m; G.resize(n+1,vector<edge>());rG.resize(n+1,vector<edge>()); rep(i,m){ int u,v,l,a;cin >> u >> v >> l >> a; G[u].push_back({v,l,a}); rG[v].push_back({u,l,a}); } R1.resize(n+1,false);R2.resize(n+1,false); dfs1(0,G,R1);dfs1(n,rG,R2); if(!R1[n]){ cout << 0 << endl; return; } dp2[0]=1; calc(n); // rep(i,n+1){ // cout << i << " " << dp1[i] << " " << dp2[i] << endl; // } if(roop) { cout << "INF" << endl; return; } cout << dp1[n] << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }