結果

問題 No.3319 Iwaijkstra
コンテスト
ユーザー DeltaStruct
提出日時 2025-10-10 23:45:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,583 bytes
コンパイル時間 2,390 ms
コンパイル使用メモリ 215,428 KB
実行使用メモリ 68,964 KB
最終ジャッジ日時 2025-10-31 19:48:24
合計ジャッジ時間 21,483 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 仮バリデーター
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
  int n,m; cin >> n >> m; vector<vector<pair<int,int>>> G(2*n),A(n); vector<vector<int>> GG(2*n);
  assert(1<=n&&n<=1e5),assert(1<=m&&m<=1e5);
  for (int i(1);i < n;++i) 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);
    assert(0<=a&&a<n),assert(0<=b&&b<c&&c<=n),assert(0<=d&&d<=1e9);
    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> 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);
    }
  }
  if (*max_element(I.begin(),I.end())) (cout<<"Too Many"<<endl),exit(0);
  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 {
    if (min(x,y)==0) return 0;
    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(i+n);k;k>>=1) --segtree[k];
      T.clear();
    }
    if (b>=n) t = a,T.emplace_back(b-n);
    for (auto c:GG[b]){
      if (dist[c]==a) dp[c] += dp[b];
      if (dist[c]>a) dist[c] = a,dp[c] = dp[b],que.emplace(dist[c],c);
    }
    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);
    }
  }
  assert(*max_element(dist.begin()+n,dist.end())!=1e18);
  cout << r << endl;
}
0