結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | どらら |
提出日時 | 2021-01-23 01:44:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 482 ms / 2,500 ms |
コード長 | 3,576 bytes |
コンパイル時間 | 2,236 ms |
コンパイル使用メモリ | 190,572 KB |
実行使用メモリ | 38,448 KB |
最終ジャッジ日時 | 2023-08-28 11:19:14 |
合計ジャッジ時間 | 14,542 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,348 KB |
testcase_01 | AC | 3 ms
8,180 KB |
testcase_02 | AC | 3 ms
8,252 KB |
testcase_03 | AC | 3 ms
8,080 KB |
testcase_04 | AC | 4 ms
8,084 KB |
testcase_05 | AC | 3 ms
8,076 KB |
testcase_06 | AC | 4 ms
8,140 KB |
testcase_07 | AC | 4 ms
8,076 KB |
testcase_08 | AC | 19 ms
9,924 KB |
testcase_09 | AC | 10 ms
9,012 KB |
testcase_10 | AC | 18 ms
9,716 KB |
testcase_11 | AC | 16 ms
9,520 KB |
testcase_12 | AC | 19 ms
9,580 KB |
testcase_13 | AC | 283 ms
28,204 KB |
testcase_14 | AC | 383 ms
30,476 KB |
testcase_15 | AC | 379 ms
31,288 KB |
testcase_16 | AC | 269 ms
24,620 KB |
testcase_17 | AC | 130 ms
20,652 KB |
testcase_18 | AC | 475 ms
36,840 KB |
testcase_19 | AC | 482 ms
36,548 KB |
testcase_20 | AC | 481 ms
37,028 KB |
testcase_21 | AC | 479 ms
36,912 KB |
testcase_22 | AC | 474 ms
37,076 KB |
testcase_23 | AC | 99 ms
16,196 KB |
testcase_24 | AC | 86 ms
13,028 KB |
testcase_25 | AC | 266 ms
23,992 KB |
testcase_26 | AC | 421 ms
31,080 KB |
testcase_27 | AC | 295 ms
24,216 KB |
testcase_28 | AC | 186 ms
20,096 KB |
testcase_29 | AC | 282 ms
23,248 KB |
testcase_30 | AC | 190 ms
20,276 KB |
testcase_31 | AC | 131 ms
17,924 KB |
testcase_32 | AC | 201 ms
21,160 KB |
testcase_33 | AC | 374 ms
28,632 KB |
testcase_34 | AC | 372 ms
30,356 KB |
testcase_35 | AC | 390 ms
32,380 KB |
testcase_36 | AC | 379 ms
31,500 KB |
testcase_37 | AC | 196 ms
19,832 KB |
testcase_38 | AC | 279 ms
24,268 KB |
testcase_39 | AC | 275 ms
24,680 KB |
testcase_40 | AC | 273 ms
24,248 KB |
testcase_41 | AC | 276 ms
24,204 KB |
testcase_42 | AC | 276 ms
24,524 KB |
testcase_43 | AC | 159 ms
38,148 KB |
testcase_44 | AC | 117 ms
29,532 KB |
testcase_45 | AC | 163 ms
38,448 KB |
testcase_46 | AC | 13 ms
14,592 KB |
testcase_47 | AC | 4 ms
8,172 KB |
ソースコード
#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]; vector<ll> rG[100005]; bool cango1[100005]; bool cango2[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}); rG[b].push_back(a); } queue<int> que; que.push(N); while(!que.empty()){ int pos = que.front(); que.pop(); if(cango1[pos]) continue; cango1[pos] = true; rep(i,rG[pos].size()){ que.push(rG[pos][i]); } } que.push(0); while(!que.empty()){ int pos = que.front(); que.pop(); if(cango2[pos]) continue; cango2[pos] = true; rep(i,G[pos].size()){ que.push(G[pos][i][0]); } } scc.scc(); 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()); vector<bool> visited(N+1,false); visited[0] = true; dp2[0] = 1; rep(ii,order.size()){ int pos = order[ii].second; if(!cango1[pos] || !cango2[pos]) continue; visited[pos] = true; rep(i,G[pos].size()){ ll to = G[pos][i][0]; ll l = G[pos][i][1]; ll a = G[pos][i][2]; if(visited[to]){ cout << "INF" << endl; return 0; } 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; }