#608540 (C++11) No.1364 [Renaming] Road to Cherry from Zelkova

提出ソース

結果

問題	No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー	leaf_1415
提出日時	2021-01-22 21:54:46
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	191 ms / 2,500 ms
コード長	4,061 bytes
コンパイル時間	2,203 ms
コンパイル使用メモリ	94,796 KB
実行使用メモリ	35,064 KB
最終ジャッジ日時	2023-08-28 11:01:37
合計ジャッジ時間	8,803 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 14,500 KB
testcase_01	AC	6 ms 14,684 KB
testcase_02	AC	6 ms 14,360 KB
testcase_03	AC	6 ms 14,408 KB
testcase_04	AC	6 ms 14,452 KB
testcase_05	AC	5 ms 14,344 KB
testcase_06	AC	6 ms 14,376 KB
testcase_07	AC	6 ms 14,412 KB
testcase_08	AC	11 ms 15,544 KB
testcase_09	AC	8 ms 14,876 KB
testcase_10	AC	12 ms 15,732 KB
testcase_11	AC	11 ms 15,120 KB
testcase_12	AC	12 ms 15,576 KB
testcase_13	AC	110 ms 27,844 KB
testcase_14	AC	158 ms 31,788 KB
testcase_15	AC	147 ms 31,328 KB
testcase_16	AC	104 ms 26,864 KB
testcase_17	AC	49 ms 21,952 KB
testcase_18	AC	185 ms 34,224 KB
testcase_19	AC	181 ms 34,136 KB
testcase_20	AC	182 ms 34,148 KB
testcase_21	AC	182 ms 34,032 KB
testcase_22	AC	184 ms 34,284 KB
testcase_23	AC	40 ms 19,404 KB
testcase_24	AC	34 ms 17,892 KB
testcase_25	AC	115 ms 26,356 KB
testcase_26	AC	191 ms 31,764 KB
testcase_27	AC	116 ms 27,516 KB
testcase_28	AC	78 ms 23,104 KB
testcase_29	AC	106 ms 27,068 KB
testcase_30	AC	90 ms 23,304 KB
testcase_31	AC	56 ms 20,712 KB
testcase_32	AC	80 ms 25,268 KB
testcase_33	AC	166 ms 30,352 KB
testcase_34	AC	174 ms 30,300 KB
testcase_35	AC	148 ms 30,188 KB
testcase_36	AC	136 ms 29,104 KB
testcase_37	AC	76 ms 23,796 KB
testcase_38	AC	101 ms 26,632 KB
testcase_39	AC	101 ms 26,504 KB
testcase_40	AC	102 ms 26,656 KB
testcase_41	AC	101 ms 26,516 KB
testcase_42	AC	99 ms 26,652 KB
testcase_43	AC	74 ms 35,064 KB
testcase_44	AC	50 ms 27,020 KB
testcase_45	AC	71 ms 33,936 KB
testcase_46	AC	11 ms 19,876 KB
testcase_47	AC	5 ms 14,420 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 1000000007

using 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-indexed
		scc.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::compG
		compG.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;
}

yukicoder

結果

テストケース

ソースコード