結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
![]() |
提出日時 | 2021-01-22 21:54:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,500 ms |
コード長 | 4,061 bytes |
コンパイル時間 | 1,557 ms |
コンパイル使用メモリ | 96,020 KB |
実行使用メモリ | 33,028 KB |
最終ジャッジ日時 | 2024-12-29 09:04:20 |
合計ジャッジ時間 | 7,350 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#include <complex>#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define all(x) (x).begin(),(x).end()#define inf 1e18#define mod 1000000007using namespace std;typedef long long llint;typedef long long ll;typedef pair<llint, llint> P;struct SCC{int n;vector<vector<int> > G, revG, compG;vector<int> used, scc, topo;int sccid, sccnum;void tpdfs(int v){used[v] = 1;for(int i = 0; i < G[v].size(); i++){if(!used[G[v][i]]) tpdfs(G[v][i]);}topo.push_back(v);}void sccdfs(int v, int id){used[v] = 1;scc[v] = id;for(int i = 0; i < revG[v].size(); i++){if(!used[revG[v][i]]) sccdfs(revG[v][i], id);}}SCC(){}SCC(int n){ //V(G) = {1, 2, ..., n}, nを制約より大きくするときは注意this->n = n;G.resize(n+1);revG.resize(n+1);used.resize(n+1);}void init(){for(int i = 1; i <= n; i++){G[i].clear(), revG[i].clear();used[i] = 0;}topo.clear();}void add_edge(int u, int v){G[u].push_back(v);}void tpsort(){topo.clear();for(int i = 1; i <= n; i++) used[i] = 0;for(int i = 1; i <= n; i++) if(!used[i]) tpdfs(i);reverse(topo.begin(), topo.end());}bool checkDAG(){ //先にtpsort()を呼ぶべし。DAGならtrueを返すfor(int i = 1; i <= n; i++) used[i] = 0;for(int i = 0; i < topo.size(); i++){int v = topo[i];used[v] = 1;for(int j = 0; j < G[v].size(); j++){if(used[G[v][j]]) return false;}}return true;}int calcSCC(){ //先にtpsort()を呼ぶべし。戻り値はSCCの個数。SCC-IDは1-indexedscc.resize(n+1);for(int i = 1; i <= n; i++) revG[i].clear();for(int i = 1; i <= n; i++){for(int j = 0; j < G[i].size(); j++){revG[G[i][j]].push_back(i);}}sccid = 1;for(int i = 1; i <= n; i++) used[i] = 0;for(int i = 0; i < topo.size(); i++) if(!used[topo[i]]) sccdfs(topo[i], sccid++);return sccnum = sccid-1;}void compressSCC(bool simple = false){ //先にcalcSCC()を呼ぶべし。圧縮後のグラフはscc::compGcompG.resize(sccnum+1);for(int i = 1; i <= n; i++){for(int j = 0; j < G[i].size(); j++){int u = G[i][j];if(scc[i] != scc[u]) compG[scc[i]].push_back(scc[u]);}}if(simple){for(int i = 1; i <= sccnum; i++){sort(compG[i].begin(), compG[i].end());compG[i].erase(unique(compG[i].begin(), compG[i].end()), compG[i].end());}}}};struct edge{ll to, cost, num;edge(){}edge(ll a, ll b, ll c){to = a, cost = b, num = c;}};ll n, m;vector<edge> G[200005], revG[200005];bool reachS[200005], reachT[200005], used[200005];ll dpnum[200005], dpsum[200005];void dfs(vector<edge> G[], ll v, bool reach[]){reach[v] = true;for(auto e : G[v]){if(reach[e.to]) continue;dfs(G, e.to, reach);}}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;ll S = n+1, T = n;n++;ll u, v, l, a;rep(i, 1, m){cin >> u >> v >> l >> a;if(u == 0) u = S;if(v == 0) v = S;G[u].push_back(edge(v, l, a));revG[v].push_back(edge(u, l, a));}dfs(G, S, reachS);dfs(revG, T, reachT);rep(i, 1, n) used[i] = !reachS[i] || !reachT[i];SCC scc(n);rep(i, 1, n){if(used[i]) continue;for(auto e : G[i]){if(used[e.to]) continue;scc.add_edge(i, e.to);}}scc.tpsort();if(!scc.checkDAG()){cout << "INF" << endl;return 0;}dpnum[S] = 1, dpsum[S] = 0;for(auto v : scc.topo){if(used[v]) continue;for(auto e : G[v]){ll u = e.to, l = e.cost, a = e.num;(dpnum[u] += dpnum[v] * a % mod) %= mod;(dpsum[u] += (dpsum[v]+dpnum[v]*l%mod)%mod * a % mod) %= mod;}}cout << dpsum[T] << endl;return 0;}