結果
問題 | No.277 根掘り葉掘り |
ユーザー | naimonon77 |
提出日時 | 2016-02-15 19:46:38 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,358 bytes |
コンパイル時間 | 1,961 ms |
コンパイル使用メモリ | 169,004 KB |
実行使用メモリ | 23,872 KB |
最終ジャッジ日時 | 2023-10-22 05:49:18 |
合計ジャッジ時間 | 6,869 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,980 KB |
testcase_01 | AC | 4 ms
8,980 KB |
testcase_02 | WA | - |
testcase_03 | AC | 4 ms
8,992 KB |
testcase_04 | AC | 4 ms
8,988 KB |
testcase_05 | AC | 4 ms
8,992 KB |
testcase_06 | AC | 4 ms
8,992 KB |
testcase_07 | WA | - |
testcase_08 | AC | 4 ms
8,980 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 distance_from_node_to_leef(int)’: main.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type] 81 | } | ^ main.cpp: In function ‘int main()’: main.cpp:89:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 89 | scanf("%d %d",&x,&y); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> #include <string> #include <set> #include <vector> #include <queue> #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) using namespace std; #define SQR(X) ((X)*(X)) #define NIL -1 struct Root { int parent,right,left,depth; }; Root tree[100005]; queue<int> qu; set<int> way[100005]; // root int distance_min = INT_MAX; int target; // 多分完成 void create_tree() { bool visited[100005] = {}; int node = 1; tree[node].depth = 0; visited[node] = true; qu.push(node); while( ! qu.empty() ) { node = qu.front(); qu.pop(); set<int>::iterator itr = way[node].begin(); set<int>::iterator past_itr = itr; for(; itr != way[node].end(); itr++) { if( ! visited[*itr] ) { tree[node].left = *itr; tree[*itr].depth = tree[node].depth+1; past_itr = itr; } } for(; itr != way[node].end(); itr++) { if( ! visited[*itr] ) { tree[*itr].depth = tree[node].depth+1; tree[*past_itr].right = *itr; past_itr = itr; } } itr--; tree[*itr].right = NIL; itr = way[node].begin(); for(; itr != way[node].end(); itr++) { if( ! visited[*itr] ) { visited[*itr] = true; qu.push(*itr); } } } } int distance_from_node_to_leef(int node) { if(tree[node].left == NIL) return 0; 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(tree[child].left == NIL) { return distance[node]+1; } else { distance[child] = distance[node]+1; qu.push(child); } } } } int main() { int i,j,k; int N; cin >> N; rep(i,N-1) { int x,y; scanf("%d %d",&x,&y); way[x].insert(y); way[y].insert(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; r = tree[i].depth; l = distance_from_node_to_leef(i); printf("%d\n",min(l,r)); } } /* void seek_distance(int current_location,int cost) { int i; int waysize = way[current_location].size(); queue<int> qu; rep(i,waysize) { int& next = way[current_location][i]; if(next == target) { distance_min = min(cost,distance_min); } if(cost+1 > distance_min) break; seek_distance(next,cost+1); } } */