結果

問題 No.3385 Up Down Hiking (C++)
コンテスト
ユーザー alcea
提出日時 2025-11-18 16:36:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 930 bytes
コンパイル時間 1,801 ms
コンパイル使用メモリ 205,328 KB
実行使用メモリ 13,540 KB
最終ジャッジ日時 2025-11-22 12:33:24
合計ジャッジ時間 12,765 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 4
other AC * 1 WA * 21 RE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
    1 | #import<bits/stdc++.h>
      |  ^~~~~~
main.cpp:5:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
    5 | main(){
      | ^~~~
main.cpp: In function ‘int main()’:
main.cpp:32:15: warning: narrowing conversion of ‘z’ from ‘long int’ to ‘int’ [-Wnarrowing]
   32 |   deque<int>D{z};
      |               ^
main.cpp:32:15: warning: narrowing conversion of ‘z’ from ‘long int’ to ‘int’ [-Wnarrowing]

ソースコード

diff #
raw source code 

#import<bits/stdc++.h>
using namespace std;
long n,m,h[1<<17],i,u,v,x[1<<17],k=-1,z,I[2],p[1<<18],t,l,d=1<<17;
vector<int>G[1<<17];
main(){
  cin>>n>>m;
  for(i=0;i<n;i++){
    cin>>h[i];
    x[i]=h[i]*d+i;
  }
  for(;cin>>u>>v;){
    u--;v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  sort(x,x+n);
  p[0]=p[d+n-1]=1;
  for(int i:x)
    for(int j:G[i%d])
      if(h[j]<h[i%d])
        for(t=0;t<2*d;t+=d)
          if(p[t+j])
            p[t+i%d]=max(p[t+i%d],p[t+j]+1);
  for(i=0;i<n;i++){
    l=p[i]+p[d+i]-1;
    if(k<l&&l>0){
      k=l;
      z=i;
    }
  }
  cout<<k<<endl;
  deque<int>D{z};
  I[0]=I[1]=z;
  I[1]+=d;
  for(;p[I[0]]+p[I[1]]>2;)
    for(t=0;t<2;t++)
      if(p[I[t]]-1)
        for(int o:G[I[t]%d])
          if(p[t*d+o]+1==p[I[t]]){
            if(t) D.push_front(o);
            else D.push_back(o);
            I[t]=o+t*d;
            break;
          }
  for(;k-->0;) cout<<D[k]+1<<" \n"[k<1];
}
0