結果
問題 | No.95 Alice and Graph |
ユーザー | asd |
提出日時 | 2015-06-13 05:08:48 |
言語 | C++11 (gcc 11.4.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,436 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 43,904 KB |
実行使用メモリ | 814,336 KB |
最終ジャッジ日時 | 2024-07-06 15:58:37 |
合計ジャッジ時間 | 3,283 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:36:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | for (scanf("%d", &T); T--; ) { | ~~~~~^~~~~~~~~~ main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:43:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | scanf("%d%d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define MX 10005 using namespace std; vector<int> adj[MX]; int N, len; int dp[MX], pr[MX]; int deg[MX]; void dfs(int u, int p, int d) { dp[u] = d; pr[u] = p; int i, v; for (i = 0; i < adj[u].size(); i++) { v = adj[u][i]; if (v != p) dfs(v, u, d + 1); } } int calc(int u, int p, int d) { int ret = 0, i, v; for (i = 0; i < adj[u].size(); i++) { v = adj[u][i]; if (v != p) ret += !!calc(v, u, d + 1); } if (d == len / 2) return deg[u] = 1; return deg[u] = ret; } int main() { int T, u, v, i, j, k; for (scanf("%d", &T); T--; ) { scanf("%d", &N); for (i = 1; i <= N; i++) { adj[i].clear(); deg[i] = 0; } for (i = 0; i < N - 1; i++) { scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } if (N == 2) { puts("NO"); continue; } len = 0; dfs(1, 0, 0); for (i = 1; i <= N; i++) len = max(len, dp[i]); for (i = 1; i <= N; i++) if (dp[i] == len) { dfs(i, 0, 0); break; } for (i = 1; i <= N; i++) len = max(len, dp[i]); k = len / 2; for (i = 1; i <= N; i++) if (dp[i] == len) { u = i; while (k--) u = pr[u]; break; } if (len & 1) { v = pr[u]; calc(u, v, 0); calc(v, u, 0); if (deg[u] == 1 || deg[v] == 1) puts("YES"); else puts("NO"); } else { calc(u, 0, 0); if (deg[u] <= 2) puts("YES"); else puts("NO"); } } return 0; }