結果

問題 No.1382 Travel in Mitaru city
ユーザー sakasu1sakasu1
提出日時 2021-02-25 17:53:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,041 bytes
コンパイル時間 1,478 ms
コンパイル使用メモリ 174,140 KB
実行使用メモリ 21,220 KB
最終ジャッジ日時 2024-10-01 08:09:21
合計ジャッジ時間 9,663 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,192 KB
testcase_01 AC 5 ms
8,192 KB
testcase_02 AC 5 ms
8,192 KB
testcase_03 AC 5 ms
8,064 KB
testcase_04 AC 5 ms
8,064 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 168 ms
16,512 KB
testcase_27 AC 161 ms
16,640 KB
testcase_28 AC 151 ms
16,640 KB
testcase_29 AC 164 ms
16,640 KB
testcase_30 AC 160 ms
16,640 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 93 ms
14,336 KB
testcase_37 AC 19 ms
8,960 KB
testcase_38 AC 105 ms
15,104 KB
testcase_39 AC 31 ms
9,728 KB
testcase_40 AC 84 ms
13,184 KB
testcase_41 AC 92 ms
13,824 KB
testcase_42 AC 111 ms
15,232 KB
testcase_43 AC 94 ms
14,336 KB
testcase_44 AC 39 ms
10,368 KB
testcase_45 AC 88 ms
13,824 KB
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 AC 8 ms
8,192 KB
testcase_62 AC 5 ms
8,064 KB
testcase_63 AC 20 ms
8,832 KB
testcase_64 AC 9 ms
8,448 KB
testcase_65 AC 5 ms
8,064 KB
testcase_66 AC 8 ms
8,320 KB
testcase_67 AC 7 ms
8,320 KB
testcase_68 AC 11 ms
8,704 KB
testcase_69 AC 7 ms
8,320 KB
testcase_70 AC 11 ms
8,576 KB
権限があれば一括ダウンロードができます

ソースコード

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(u>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