結果

問題 No.95 Alice and Graph
コンテスト
ユーザー asd
提出日時 2015-06-13 05:08:48
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 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);
      |                         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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;
}
0