結果

問題 No.3013 ハチマキ買い星人
ユーザー kino0402
提出日時 2025-01-25 13:19:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 502 ms / 2,000 ms
コード長 7,832 bytes
コンパイル時間 8,911 ms
コンパイル使用メモリ 448,020 KB
実行使用メモリ 34,140 KB
最終ジャッジ日時 2025-01-25 22:42:57
合計ジャッジ時間 22,144 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:227:26: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
  227 | vecll dijkstra(ll N,ll S,auto G){
      |                          ^~~~
main.cpp:264:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
  264 | void warshall_floyd(auto &dis){
      |                     ^~~~
main.cpp:273:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
  273 | vecll zahyouassyuku(auto X){
      |                     ^~~~
main.cpp:282:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  282 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all> 
using namespace std;
using namespace atcoder;
using ll=long long;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define doubleketa(i) cout<<fixed<<setprecision(i);
#define speedup std::cin.tie(0)->sync_with_stdio(0);
#define _GLIBCXX_DEBUG //優先度付きキュー使って時間制限厳しい場合コメントアウト
//#define int ll
#define int_max 2147483647
#define int_min -2147483647
#define uint_max 4294967295
#define ll_max 9223372036854775807
#define ll_min -9223372036854775807
#define ull_max 18446744073709551615
#define rep(i,n) for(ll i=0;i<(n);i++)
#define reps(i,n) for(ll i=1;i<=(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(n);i++)
#define all(a) (a).begin(), (a).end()
#define repc(i,n,A) rep(i,n)cin>>A[i]
#define REPC(i,j,n,A) REP(i,j,n)cin>>A[i]
#define repc2(i,n,A,B) rep(i,n)cin>>A[i]>>B[i]
#define REPC2(i,j,n,A,B) REP(i,j,n)cin>>A[i]>>B[i]
#define repc2vec(i,j,a,b,A) rep(i,a)rep(j,b)cin>>A[i][j]
#define REPC2VEC(i,j,k,a,b,A) REP(i,k,a)REP(j,k,b)cin>>A[i][j]
#define repair(i,n,A) rep(i,n)cin>>A[i].F>>A[i].S
#define REPAIR(i,j,n,A) REP(i,j,n)cin>>A[i].F>>A[i].S
#define ST(A) sort(all(A))
#define RV(A) reverse(all(A))
#define juufuku(A) A.erase(unique(all(A)),A.end());
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define Endl endl
#define F first
#define S second
#define yes(b) ((b)?"yes":"no")
#define Yes(b) ((b)?"Yes":"No")
#define YES(b) ((b)?"YES":"NO")
#define TA(b) ((b)?"Takahashi":"Aoki")
#define AB(b) ((b)?"Alice":"Bob")
using vecll=vector<ll>; using vecst=vector<string>; using vecch=vector<char>;
using vecll2=vector<vecll>; using vecst2=vector<vecst>; using pll=pair<ll,ll>;
using vecch2=vector<vecch>; using vecpll=vector<pll>; using vecpll2=vector<vecpll>;
using vecbo=vector<bool>; using vecbo2=vector<vecbo>;
using vecdo=vector<double>; using vecdo2=vector<vecdo>;
using pq=priority_queue<ll>; using pqp=priority_queue<pll>;
using pqg=priority_queue<ll,vecll,greater<ll>>;
using pqpg=priority_queue<pll,vecpll,greater<pll>>;
template <typename T> inline T gcd(T a,T b){return (b==0)?a:gcd(b,a%b);}//最大公約数
template <typename T> inline T lcm(T a,T b){return (a*b)/gcd(a,b);}//最小公倍数
template <typename T>
bool chmax(T &a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a,const T& b){
  if(a>b){
    a=b;  // aをbで更新
    return true;
  }
  return false;
}
ll max(int a,ll b){return max((ll)a,b);}
ll max(ll a,int b){return max((ll)b,a);}
ll min(int a,ll b){return min((ll)a,b);}
ll min(ll a,int b){return min((ll)b,a);}
vecll DX={0,1,0,-1,1,1,-1,-1};
vecll DY={1,0,-1,0,1,-1,1,-1};
ll mod=998244353;
ll modgyakugen=499122177;
ll MOD=1000000007;
ll INF=1e18;
template<ll char_size,ll base>
struct Trie{
  struct Node{            // 頂点を表す構造体
    vecll next;    // 子の頂点番号を格納。存在しなければ-1
    vecll accept;  // 末端がこの頂点になる単語の word_id を保存
    ll c;               // base からの間隔をll型で表現したもの
    ll common;          // いくつの単語がこの頂点を共有しているか
    Node(ll c_):c(c_),common(0){
      next.assign(char_size,-1);
    }
  };
  vector<Node>nodes;  // trie木本体
  ll root;
  Trie():root(0){
    nodes.pb(Node(root));
  }
  //単語の挿入
  void insert(const string &word,ll word_id){
    ll node_id=0;
    rep(i,word.size()){
      ll c=(ll)(word[i]-base);
      ll &next_id=nodes[node_id].next[c];
      if(next_id==-1){// 次の頂点が存在しなければ追加
        next_id=(ll)nodes.size();
        nodes.pb(Node(c));
      }
      ++nodes[node_id].common;
      node_id = next_id;
    }
    ++nodes[node_id].common;
    nodes[node_id].accept.pb(word_id);
  }
  void insert(const string &word){
    insert(word,nodes[0].common);
  }
  //単語とprefixの検索
  bool search(const string &word,bool prefix=false){
    ll node_id = 0;
    rep(i,word.size()){
      ll c=(ll)(word[i]-base);
      ll &next_id=nodes[node_id].next[c];
      if(next_id==-1){  // 次の頂点が存在しなければ終了
        return false;
      }
      node_id = next_id;
    }
    return(prefix)?true:nodes[node_id].accept.size()>0;
  }
  //prefixを持つ単語が存在するかの検索
  bool start_with(const string &prefix){
    return search(prefix,true);
  }
  //挿入した単語の数
  int count() const{
    return(nodes[0].common);
  }
  //Trie木のノード数
  int size() const{
    return ((ll)nodes.size());
  }
};
ll randint(ll a,ll b){return a+rand()%(b-a+1);}
double randouble(){return 1.0*rand()/RAND_MAX;}
ll nibutanl(ll K,vecll& V){
  //二分探索
  ll ng=-1;
  ll ok=V.size();
  while(ok-ng>1){
    ll m=(ng+ok)/2;
    if(V[m]>=K)ok=m;
    else ng=m;
  }
  return ok;
}
ll nibutanu(ll K,vecll& V){
  //二分探索
  ll ng=-1;
  ll ok=V.size();
  while(ok-ng>1){
    ll m=(ng+ok)/2;
    if(V[m]>K)ok=m;
    else ng=m;
  }
  return ok;
}
ll dist(ll x1,ll y1,ll x2,ll y2){
  return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
ll digit_sum(ll n){
  ll sum=0;
  while(n){
    sum+=n%10;
    n/=10; 
  }
  return sum;
}
vecpll soinsuubunkai(ll N){
  vecpll res;
  for(ll a=2;a*a<=N;a++){
    if(N%a!=0)continue;
    int ex=0;//指数
    //割れる限り割る
    while(N%a==0){
      ex++;
      N/=a;
    }
    //結果をpb
    res.pb({a,ex});
  }
    //後に残った数について
  if(N!=1)res.pb({N,1});
  return res;
  //N=6 {2,1} {3,1}(2^1*3^1)のようになる autoで受け取ろう
}
vecll yakusuurekkyo(ll N){
  //答えを表す集合
  vecll res;
  //各整数iがNの約数かどうかを調べる
  for (ll i=1;i*i<=N;++i){
    //iがNの約数でない場合はスキップ
    if(N%i!=0)continue;
    //iは約数である
    res.pb(i);
    //N÷iも約数である(重複に注意)
    if(N/i!=i)res.pb(N/i);
  }
  //約数をソートして出力
  ST(res);
  return res;
}
ll ketasuu(ll num){
	ll digit=0;
	while(num!=0){
		num/=10;
		digit++;
	}
	return digit;
}
vecll dijkstra(ll N,ll S,auto G){
  vecll dis(N,ll_max);
  vecbo vis(N);
  pqpg Q;
  dis[S]=0;
  Q.push(mp(0,S));
  while(!Q.empty()){
    ll pos=Q.top().S;Q.pop();
    if(vis[pos]==true)continue;
    vis[pos]=true;
    rep(i,G[pos].size()){
      ll nex=G[pos][i].F;
      ll cost=G[pos][i].S;
      if(dis[nex]>dis[pos]+cost){
        dis[nex]=dis[pos]+cost;
        Q.push(mp(dis[nex],nex));
      }
    }
  }
  return dis;
}
vecll ruisekiwa(vecll V){
  vecll A(V.size()+1);
  rep(i,V.size())A[i+1]=A[i]+V[i];
  return A;
}
vecbo furui(ll N) {
  vecbo isprime(N+1,true);
  isprime[1]=false;
  for(ll p=2;p<=N;++p){
    if(!isprime[p])continue;
    for(ll q=p*2;q<=N;q+=p){
      isprime[q]=false;
    }
  }
  return isprime;
}
void warshall_floyd(auto &dis){
  rep(k,dis.size()){
    rep(i,dis.size()){
      rep(j,dis.size()){
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
      }
    }
  }
}
vecll zahyouassyuku(auto X){
  vecll x=X;
  ST(x);
  juufuku(x);
  vecll ans(X.size());
  rep(i,X.size())ans[i]=lower_bound(all(x),X[i])-x.begin();
  return ans;
}
//ここからコード入力(　　　´・ω・｀     )
main(){
  ll A,B,C,D,t1,t2,t3,ans=0;
  cin>>A>>B>>C>>D;
  vecpll2 G(A);
  rep(i,B){
    cin>>t1>>t2>>t3;
    G[t1-1].eb(mp(t2-1,t3));
    G[t2-1].eb(mp(t1-1,t3));
  }
  vecll E=dijkstra(A,0,G);
  rep(i,C){
    cin>>t1>>t2;
    ans=max(ans,(D-E[t1-1])/t2);
  }
  cout<<ans<<endl;
}
0