結果

問題 No.2948 move move rotti
コンテスト
ユーザー GOTKAKO
提出日時 2024-10-26 15:18:02
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,107 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 978 ms
コンパイル使用メモリ 208,284 KB
最終ジャッジ日時 2026-07-06 02:07:01
合計ジャッジ時間 1,920 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_algobase.h:76,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/algorithm:62,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:53,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bit: In instantiation of 'constexpr int std::__popcount(_Tp) [with _Tp = int]':
main.cpp:21:52:   required from here
   21 |     for(int i=0; i<n2; i++) ones.at(i) = __popcount(i);
      |                                          ~~~~~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bit:308:34: error: argument 1 in call to function '__builtin_popcountg' has signed type
  308 |       return __builtin_popcountg(__x);
      |                                  ^~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M,K; cin >> N >> M >> K;
    vector<int> X(K);
    for(auto &x : X) cin >> x,x--;
    vector<vector<int>> Graph(N);
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }

    int n2 = 1<<N;
    vector<int> ones(n2);
    for(int i=0; i<n2; i++) ones.at(i) = __popcount(i);

    vector<vector<int>> ok(N,vector<int>(N));
    int idx = 0;
    for(auto &start : X){
        vector dp(N,vector<bool>(n2));
        dp.at(start).at(1<<start) = true;
        for(int k=0; k<n2; k++) for(int i=0; i<N; i++){
            if(dp.at(i).at(k) == false) continue;
            ok.at(i).at(ones.at(k)-1) |= (1<<idx);
            for(auto to : Graph.at(i)){
                if(k&(1<<to)) continue;
                dp.at(to).at(k+(1<<to)) = true;
            }
        }
        idx++;
    }
    for(auto &o : ok) for(auto &v : o) if(v == (1<<K)-1){cout << "Yes\n"; return 0;}
    cout << "No\n";
}
0