結果

問題 No.1153 ねこちゃんゲーム
ユーザー Caiiiiiiii
提出日時 2025-07-12 15:59:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 310 ms / 2,500 ms
コード長 1,429 bytes
コンパイル時間 2,602 ms
コンパイル使用メモリ 194,840 KB
実行使用メモリ 60,928 KB
最終ジャッジ日時 2025-07-12 15:59:53
合計ジャッジ時間 20,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:48:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:50:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
main.cpp:52:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |     scanf("%d%d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using LL = long long;

const int N = 2e5 + 7;
const int L = 19;

int n, m, a[N], sgsub[N], sg[N], f[N][L], g[N][L];
std::vector<int> e[N];

void dfs(int x, int y) {
  for(int v: e[x])
    if(v != y) {
      dfs(v, x);
      f[x][sgsub[v]] = 1;
    }
  while(f[x][sgsub[x]])
    ++sgsub[x];
}

void dfs2(int x, int y) {
  if(x == 1) {
    for(auto v: e[x]) {
      ++f[x][sgsub[v]];
      g[x][sgsub[v]] = std::min(g[x][sgsub[v]], v);
    }
    sg[x] = sgsub[x];
  }
  else {
    int sgy = sgsub[x] > sg[y] || f[y][sgsub[x]] > 1 ? sg[y] : sgsub[x];
    ++f[x][sgy];
    g[x][sgy] = y;
    for(auto v: e[x])
      if(v != y) {
	++f[x][sgsub[v]];
	g[x][sgsub[v]] = std::min(g[x][sgsub[v]], v);
      }
    while(f[x][sg[x]])
      ++sg[x];
  }
  for(auto v: e[x])
    if(v != y)
      dfs2(v, x);
}

int main() {

  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i)
    scanf("%d", &a[i]);
  for(int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }

  dfs(1, 0);
  memset(f, 0, sizeof f);
  memset(g, 0x3f, sizeof g);
  dfs2(1, 0);

  int val = 0;
  for(int i = 1; i <= m; ++i)
    val ^= sg[a[i]];

  if(!val) {
    puts("-1 -1");
    return 0;
  }

  for(int i = 1; i <= m; ++i) 
    if((val ^ sg[a[i]]) < L && f[a[i]][val ^ sg[a[i]]]) {
      printf("%d %d\n", i, g[a[i]][val ^ sg[a[i]]]);
      return 0;
    }

  assert(0);
  
  return 0; 

}
0