結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | どらら |
提出日時 | 2021-01-23 01:15:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,931 bytes |
コンパイル時間 | 1,908 ms |
コンパイル使用メモリ | 186,208 KB |
実行使用メモリ | 32,548 KB |
最終ジャッジ日時 | 2023-08-28 10:30:41 |
合計ジャッジ時間 | 13,458 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,852 KB |
testcase_01 | AC | 3 ms
5,660 KB |
testcase_02 | AC | 3 ms
5,708 KB |
testcase_03 | AC | 3 ms
5,788 KB |
testcase_04 | AC | 3 ms
5,688 KB |
testcase_05 | AC | 3 ms
5,648 KB |
testcase_06 | AC | 3 ms
5,660 KB |
testcase_07 | AC | 3 ms
5,736 KB |
testcase_08 | AC | 17 ms
7,528 KB |
testcase_09 | AC | 9 ms
6,368 KB |
testcase_10 | AC | 17 ms
7,020 KB |
testcase_11 | AC | 15 ms
6,944 KB |
testcase_12 | AC | 18 ms
7,104 KB |
testcase_13 | AC | 250 ms
24,292 KB |
testcase_14 | AC | 329 ms
25,412 KB |
testcase_15 | AC | 338 ms
26,868 KB |
testcase_16 | AC | 230 ms
20,376 KB |
testcase_17 | AC | 120 ms
18,164 KB |
testcase_18 | AC | 458 ms
32,172 KB |
testcase_19 | AC | 448 ms
32,296 KB |
testcase_20 | AC | 469 ms
32,324 KB |
testcase_21 | AC | 455 ms
32,120 KB |
testcase_22 | AC | 473 ms
32,156 KB |
testcase_23 | AC | 84 ms
12,236 KB |
testcase_24 | AC | 81 ms
9,904 KB |
testcase_25 | AC | 223 ms
18,868 KB |
testcase_26 | AC | 354 ms
24,664 KB |
testcase_27 | AC | 259 ms
19,228 KB |
testcase_28 | AC | 154 ms
15,452 KB |
testcase_29 | AC | 246 ms
18,896 KB |
testcase_30 | AC | 167 ms
15,736 KB |
testcase_31 | AC | 114 ms
13,468 KB |
testcase_32 | AC | 191 ms
16,932 KB |
testcase_33 | AC | 323 ms
22,964 KB |
testcase_34 | AC | 311 ms
23,684 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 189 ms
15,524 KB |
testcase_38 | AC | 262 ms
18,928 KB |
testcase_39 | AC | 261 ms
19,168 KB |
testcase_40 | AC | 260 ms
19,004 KB |
testcase_41 | AC | 264 ms
19,104 KB |
testcase_42 | AC | 261 ms
19,248 KB |
testcase_43 | AC | 143 ms
32,548 KB |
testcase_44 | AC | 107 ms
23,660 KB |
testcase_45 | AC | 138 ms
29,864 KB |
testcase_46 | AC | 13 ms
12,292 KB |
testcase_47 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; class SCC { int V; std::vector<std::vector<int>> G, rG; std::vector<int> vs; std::vector<bool> used; std::vector<int> cmp; void dfs(int v){ used[v] = true; for(int i=0; i<G[v].size(); i++) if(!used[G[v][i]]) dfs(G[v][i]); vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i=0; i<rG[v].size(); i++) if(!used[rG[v][i]]) rdfs(rG[v][i], k); } public: SCC(int V):V(V),G(V),rG(V),used(V),cmp(V){} int size(){ return V; } std::vector<int> get_edge(int from){ return G[from]; } void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } // 強連結成分(2点が相互に行き来できるグループ)数 int scc(){ for(int i=0; i<used.size(); i++) used[i] = 0; vs.clear(); for(int v=0; v<V; v++) if(!used[v]) dfs(v); for(int i=0; i<used.size(); i++) used[i] = 0; int k = 0; for(int i=vs.size()-1; i>=0; i--) if(!used[vs[i]]) rdfs(vs[i], k++); return k; } // サイクルがあるか bool iscyclic(){ return scc() != V; } // 強連結成分番号 std::vector<int> get_cmp(){ return cmp; } // 同じ辺を2度通らない、その頂点までの最長経路 std::vector<int> depth(){ scc(); std::vector<pair<int,int>> order; std::vector<int> dp(V, 1); for(int i=0; i<V; i++){ order.push_back(make_pair(cmp[i],i)); } std::sort(order.begin(), order.end()); for(int i=0; i<V; i++){ int node = order[i].second; for(int j=0; j<G[node].size(); j++){ dp[G[node][j]] = max(dp[G[node][j]], dp[node]+1); } } return dp; } }; static const ll MOD = 1000000007; vector<vector<ll>> G[100005]; ll dp1[100005]; ll dp2[100005]; int main(){ int N, M; cin >> N >> M; SCC scc(N+1); rep(i,M){ ll a, b, c, d; cin >> a >> b >> c >> d; scc.add_edge(a,b); G[a].push_back({b, c % MOD, d % MOD}); } scc.scc(); if(scc.iscyclic()){ cout << "INF" << endl; return 0; } vector<int> cmp = scc.get_cmp(); vector<pair<int,int>> order; for(int i=0; i<cmp.size(); i++){ order.push_back(make_pair(cmp[i],i)); } sort(order.begin(), order.end()); dp2[0] = 1; rep(ii,order.size()){ int pos = order[ii].second; rep(i,G[pos].size()){ ll to = G[pos][i][0]; ll l = G[pos][i][1]; ll a = G[pos][i][2]; dp1[to] += ((dp1[pos] * a)%MOD + (((a * dp2[pos]) % MOD) * l) % MOD) % MOD; dp1[to] %= MOD; dp2[to] += (dp2[pos] * a) % MOD; dp2[to] %= MOD; } } cout << dp1[N] << endl; return 0; }