結果

問題 No.629 グラフの中に眠る門松列
コンテスト
ユーザー Kou0406
提出日時 2025-02-26 11:06:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 4,000 ms
コード長 1,321 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 77,040 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-26 11:06:49
合計ジャッジ時間 2,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:14:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:17:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |     rep(i,n)scanf("%d",&a[i]);
      |             ~~~~~^~~~~~~~~~~~
main.cpp:19:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |         scanf("%d%d",&i,&j);
      |         ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#define rep(i,n) for(i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n,m;

int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    vector<int> a(n);
    vector<vector<int> > adj(n,vector<int>(0));
    rep(i,n)scanf("%d",&a[i]);
    while(m--){
        scanf("%d%d",&i,&j);
        i--;j--;
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    vector<int> path;
    vector<bool> vis(n,false);
    auto dfs=[&](auto& f,int now)->bool{
        path.push_back(now);
        vis[now]=true;
        if(path.size()==3){
            int data[]={0,1,2};
            sort(data,data+3,[&](int i,int j)->bool{
                return a[path[i]]<a[path[j]];
            });
            vis[now]=false;
            path.pop_back();
            return data[0]==1||data[2]==1;
        }
        int i,j;
        rep(i,adj[now].size()){
            if(vis[adj[now][i]]==false){
                rep(j,path.size())if(a[path[j]]==a[adj[now][i]])break;
                if(j==path.size()&&f(f,adj[now][i]))return true;
            }
        }
        vis[now]=false;
        path.pop_back();
        return false;
    };
    rep(i,n)if(dfs(dfs,i))break;
    printf("%s\n",i==n?"NO":"YES");
    return 0;
}
0