結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー leaf_1415leaf_1415
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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()DAGtrue
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()SCCSCC-ID1-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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0