結果

問題 No.408 五輪ピック
コンテスト
ユーザー yuppe19 😺
提出日時 2017-10-19 23:08:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,063 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 52,388 KB
最終ジャッジ日時 2024-11-14 20:15:17
合計ジャッジ時間 1,018 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:17:3: error: ‘vector’ was not declared in this scope
   17 |   vector<vector<int>> G(n, vector<int>());
      |   ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <algorithm>
  +++ |+#include <vector>
    3 | using namespace std;
main.cpp:17:17: error: expected primary-expression before ‘int’
   17 |   vector<vector<int>> G(n, vector<int>());
      |                 ^~~
main.cpp:21:5: error: ‘G’ was not declared in this scope
   21 |     G[a].push_back(b);
      |     ^
main.cpp:25:12: error: expected primary-expression before ‘int’
   25 |     vector<int> colour(n); // colour[n]
      |            ^~~
main.cpp:27:7: error: ‘colour’ was not declared in this scope
   27 |       colour[i] = xorshift32() % 5;
      |       ^~~~~~
main.cpp:29:19: error: expected primary-expression before ‘bool’
   29 |     vector<vector<bool>> dp(n, vector<bool>(1<<5, false)); // dp[n][1<<5]
      |                   ^~~~
main.cpp:30:5: error: ‘dp’ was not declared in this scope
   30 |     dp[0][0] = true;
      |     ^~
main.cpp:34:21: error: ‘G’ was not declared in this scope
   34 |         for(int u : G[v]) { // v から u へ
      |                     ^
main.cpp:35:22: error: ‘colour’ was not declared in this scope
   35 |           if(mask >> colour[u] & 1) { continue; }
      |                      ^~~~~~
main.cpp:36:26: error: ‘colour’ was not declared in this scope
   36 |           dp[u][mask|(1<<colour[u])] = true;
      |                          ^~~~~~
main.cpp:16:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |   int n, m; scanf("%d%d", &n, &m);
      |             ~~~~~^~~~~~~~~~~~~~~~
main.cpp:19:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ��

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;
using u32 = unsigned int;

u32 uy = time(NULL);
u32 xorshift32() {
  uy ^= uy << 13;
  uy ^= uy >> 17;
  uy ^= uy << 5;
  return uy;
}

int main(void) {
  int n, m; scanf("%d%d", &n, &m);
  vector<vector<int>> G(n, vector<int>());
  for(int i=0; i<m; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for(int loop=0; loop<300; ++loop) {
    vector<int> colour(n); // colour[n]
    for(int i=0; i<n; ++i) {
      colour[i] = xorshift32() % 5;
    }
    vector<vector<bool>> dp(n, vector<bool>(1<<5, false)); // dp[n][1<<5]
    dp[0][0] = true;
    for(int mask=0; mask<1<<5; ++mask) {
      for(int v=0; v<n; ++v) {
        if(!dp[v][mask]) { continue; }
        for(int u : G[v]) { // v から u へ
          if(mask >> colour[u] & 1) { continue; }
          dp[u][mask|(1<<colour[u])] = true;
        }
      }
    }
    if(dp[0][(1<<5)-1]) {
      puts("YES");
      return 0;
    }
  }
  puts("NO");
  return 0;
}
0