結果
問題 |
No.1153 ねこちゃんゲーム
|
ユーザー |
|
提出日時 | 2025-07-12 15:48:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,405 bytes |
コンパイル時間 | 2,284 ms |
コンパイル使用メモリ | 194,968 KB |
実行使用メモリ | 60,672 KB |
最終ジャッジ日時 | 2025-07-12 15:48:32 |
合計ジャッジ時間 | 23,263 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 WA * 1 |
コンパイルメッセージ
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); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#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(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; }