結果
問題 | No.277 根掘り葉掘り |
ユーザー | naimonon77 |
提出日時 | 2016-02-16 21:26:50 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,616 bytes |
コンパイル時間 | 719 ms |
コンパイル使用メモリ | 76,524 KB |
実行使用メモリ | 15,396 KB |
最終ジャッジ日時 | 2023-10-22 06:01:37 |
合計ジャッジ時間 | 5,571 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
14,040 KB |
testcase_01 | AC | 3 ms
7,028 KB |
testcase_02 | AC | 3 ms
7,028 KB |
testcase_03 | AC | 3 ms
7,028 KB |
testcase_04 | AC | 3 ms
7,032 KB |
testcase_05 | AC | 3 ms
7,028 KB |
testcase_06 | AC | 3 ms
7,028 KB |
testcase_07 | AC | 3 ms
7,032 KB |
testcase_08 | AC | 3 ms
7,028 KB |
testcase_09 | TLE | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:129:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 129 | scanf("%d %d",&x,&y); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <cstring> #include <algorithm> #include <limits.h> #include <cmath> #include <cstdio> #include <vector> #include <set> #include <string> #include <queue> #include <cstdlib> #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define NIL -1 struct Root { int parent,right,left,depth; }; Root tree[100005]; queue<int> qu; vector<int> way[100005]; // root int distance_min = INT_MAX; int target; void create_tree() { int i; bool visited[100005] = {}; int node = 1; tree[node].depth = 0; visited[node] = true; qu.push(node); while( ! qu.empty() ) { node = qu.front(); qu.pop(); int past_child = way[node][0]; for(i=0; i < way[node].size(); i++) { int child = way[node][i]; if( ! visited[child] ) { tree[node].left = child; tree[child].depth = tree[node].depth+1; tree[child].parent = node; past_child = child; break; } } i++; for(; i < way[node].size(); i++) { int child = way[node][i]; if( ! visited[child] ) { tree[child].depth = tree[node].depth+1; tree[child].parent = node; tree[past_child].right = child; past_child = child; } } tree[i-1].right = NIL; for(i=0; i < way[node].size(); i++) { int child = way[node][i]; if( ! visited[child] ) { visited[child] = true; qu.push(child); } } } } int distance_from_node_to_leef(int node) { int test = 0; while (!qu.empty()) qu.pop(); if(test) puts(""); if(test) printf(" node %d\n",node); if(tree[node].left == NIL) return 0; if(test) printf("tree[node].left = %d\n",tree[node].left); int distance[100005]; bool visited[100005] = {}; visited[node] = true; distance[node] = 0; qu.push(node); while( ! qu.empty() ) { node = qu.front(); qu.pop(); int child = tree[node].left; for(; child != NIL; child = tree[child].right) { if(test) printf("child = %d\n",child); if(visited[child] == false) { if(tree[child].left == NIL) { return distance[node]+1; } else if(visited[child] == false){ visited[child] = true; distance[child] = distance[node]+1; qu.push(child); if(test) printf("qu.push(%d)\n",child); } } } int parent = tree[node].parent; if(parent != NIL && visited[parent] == false) { visited[parent] = true; distance[parent] = distance[node]+1; qu.push(parent); } } return INT_MIN; } int main() { int i,j,k; int N;/* freopen("test_in\2_small_03","r",stdin); FILE *fp = fopen("test_out\2_small_03","r"); if(fp == NULL) { puts("ファイルオープンエラー"); exit(1); }*/ cin >> N; rep(i,N-1) { int x,y; scanf("%d %d",&x,&y); way[x].push_back(y); way[y].push_back(x); } rep(i,N+1) { tree[i].parent = NIL; tree[i].right = NIL; tree[i].left = NIL; } create_tree(); puts("0"); for(i=2;i<N+1;i++) { int r,l;/* printf("node%d : ",i); printf("parent = %2d ",tree[i].parent); printf("left = %2d ",tree[i].left); printf("right = %2d",tree[i].right); puts("");*/ r = tree[i].depth; l = distance_from_node_to_leef(i); int ans; // fscanf(fp,"%d",&ans); printf("%d",min(r,l)); // printf(" ans = %d",ans); puts(""); // printf("r = %d l = %d\n",r,l); } }