結果

問題 No.3319 Iwaijkstra
コンテスト
ユーザー DeltaStruct
提出日時 2025-07-27 14:10:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,485 bytes
コンパイル時間 2,804 ms
コンパイル使用メモリ 216,900 KB
実行使用メモリ 72,820 KB
最終ジャッジ日時 2025-10-31 19:47:24
合計ジャッジ時間 23,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 19 WA * 35 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long

void dfs(vector<vector<int>>& G,int x,int r,vector<int>& vis){
  if (vis[x]==r) (cout<<"Too Many"<<endl),exit(0);
  if (vis[x]) return;
  vis[x] = r;
  for (int y:G[x]) dfs(G,y,r,vis);
}

signed main(){
  int n,m; cin >> n >> m; vector<vector<pair<int,int>>> G(2*n),A(n); vector<vector<int>> GG(2*n);
  for (int i(1);i < n;++i){
    G[i].emplace_back(i<<1,0),G[i].emplace_back(i<<1|1,0),GG[i].emplace_back(i<<1),GG[i].emplace_back(i<<1|1);
  }
  for (int i(0),a,b,c,d;i < m;++i){
    cin >> a >> b >> c >> d; --a,--b; A[a].emplace_back(b,c);
    if (d) for (int l(n+b),r(n+c);l < r;l>>=1,r>>=1){
      if (l&1) G[n+a].emplace_back(l++,d);
      if (r&1) G[n+a].emplace_back(--r,d);
    } else for (int l(n+b),r(n+c);l < r;l>>=1,r>>=1){
      if (l&1) GG[n+a].emplace_back(l++);
      if (r&1) GG[n+a].emplace_back(--r);
    }
  }
  vector<int> vis(2*n);
  for (int i(0);i < n;++i) if (vis[n+i]==0) dfs(GG,n+i,i+1,vis);
  vector<int> I(2*n),O(2*n,-1); int o = 0; for (int i(0);i < 2*n;++i) for (int k:GG[i]) ++I[k];
  queue<int> q; for (int i(0);i < 2*n;++i) if (I[i]==0) q.emplace(i);
  while(!q.empty()){
    int x = q.front(); q.pop(),O[x] = o++;
    for (int y:GG[x]){
      --I[y];
      if (I[y]==0) q.emplace(y);
    }
  }
  auto f = [&O](pair<int,int>& x,pair<int,int>& y) -> bool {
    return (x.first==y.first?O[x.second]>O[y.second]:x.first>y.first);
  };
  vector<int> dist(2*n,1e18),dp(2*n),segtree(2*n,1); int r = 1;
  for (int i(n-1);i;--i) segtree[i] = segtree[i<<1]+segtree[i<<1|1];
  priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(f)> que(f);
  dist[n] = 0,dp[n] = 1,que.emplace(0,n); int t = 0; vector<int> T;
  auto check = [](int x,int y) -> int {
    int t = 1e18; if (x>t||y>t||y>t/x) (cout<<"Too Many"<<endl),exit(0);
    return x*y;
  };
  while(!que.empty()){
    auto [a,b] = que.top(); que.pop();
    if (dist[b]!=a) continue;
    if (t!=a){
      for (int i:T) for (int k(n+i);k;k>>=1) --segtree[k];
      T.clear();
    }
    if (b>=n) t = a,T.emplace_back(b-n);
    for (auto [c,d]:G[b]){
      if (dist[c]==a+d) dp[c] += dp[b];
      if (dist[c]>a+d) dist[c] = a+d,dp[c] = dp[b],que.emplace(dist[c],c);
    }
    if (b>=n) for (auto [ll,rr]:A[b-n]) for (ll+=n,rr+=n;ll < rr;ll>>=1,rr>>=1){
      if (ll&1) r += check(segtree[ll++],dp[b]);
      if (rr&1) r += check(segtree[--rr],dp[b]);
      if (r>1e18) (cout<<"Too Many"<<endl),exit(0);
    }
  }
  cout << r << endl;
}
0