結果

問題 No.1382 Travel in Mitaru city
ユーザー sakasu1sakasu1
提出日時 2021-02-25 17:49:39
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,044 bytes
コンパイル時間 1,538 ms
コンパイル使用メモリ 174,384 KB
実行使用メモリ 21,032 KB
最終ジャッジ日時 2024-10-01 08:05:46
合計ジャッジ時間 9,830 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> P;
struct unionfind{
  int par[400010]; // 親ノード  必要に応じて要素数を変えよう
  int rank[400010]; // ランク　必要に応じて要素数を変えよう
  int w[400010];
  unionfind(int n){
    init(n);
  }
  void init(int n){
    for(int i=0;i<=n;i++){
      par[i]=i;
      rank[i]=1;
      w[i]=0;
    }
  }
  int root(int x) {
    if (par[x] == x) {
      return x;
    }
    else {
      return par[x] = root(par[x]);
    }
  }
  int size(int x){
    return rank[root(x)];
  }
  bool same(int x,int y) {
    return root(x) == root(y);
  }
  void unite(int x,int y) {
    x=root(x);
    y=root(y);
    if(x==y){
      w[x]++;
      return;
    }
    if(rank[x]<rank[y]){
      swap(x,y);
    }
    rank[x]=rank[x]+rank[y];
    par[y]=x;
    w[x]+=w[y];
    w[x]++;
  }
  int wsize(int x){
    return w[root(x)];
  }
};
int main(){
  const ll INF=1000000000;
  ll i,n,m,s,t;
  cin >> n >> m >> s >> t;
  s--,t--;
  unionfind tree(n);
  vector<ll> p(n);
  for(i=0;i<n;i++){
    cin >> p[i];
  }
  vector<vector<ll> > g(n);
  for(i=0;i<m;i++){
    ll a,b;
    cin >> a >> b;
    a--,b--;
    tree.unite(a,b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<ll> ds(n,-INF),ns(n,0);
  ds[s]=0,ns[s]=1;
  priority_queue<P> que;
  que.push(P(pll(p[s],0),s));
  while(!que.empty()){
    P p1=que.top();
    que.pop();
    ll u=p1.first.first,v=p1.first.second;
    ll r=p1.second;
    if(ds[r]!=v){
      continue;
    }
    for(i=0;i<g[r].size();i++){
      ll us=g[r][i];
      if(p[s]>p[us]){
        if(ds[us]<ds[r]+1 && ns[us]==0){
          ds[us]=ds[r]+1;
          que.push(P(pll(p[us],ds[us]),us));
        }
      }
      else{
        if(ds[us]<ds[r] && ns[us]==0){
          ds[us]=ds[r];
          que.push(P(pll(u,ds[us]),us));
        }
      }
    }
    ns[r]=1;
  }
  ll ans=0;
  for(i=0;i<n;i++){
    if(tree.same(i,t)){
      ans=max(ans,ds[i]);
    }
  }
  cout << ans << endl;
}
0