結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-11-03 23:48:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 237 ms / 3,000 ms |
コード長 | 2,128 bytes |
コンパイル時間 | 1,077 ms |
コンパイル使用メモリ | 99,624 KB |
実行使用メモリ | 17,864 KB |
最終ジャッジ日時 | 2024-09-13 12:20:57 |
合計ジャッジ時間 | 5,539 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <ctime>#include <fstream>#include <queue>#include <complex>#define INF 100000000#define INF_INT_MAX 2147483647#define INF_LL_MAX 9223372036854775807#define EPS 1e-10#define Pi acos(-1)#define LL long long#define ULL unsigned long longusing namespace std;#define MAX_N 100005int N;vector<int> Edge[MAX_N];class cNode{public:int RootLength;int LeafLength;bool LeafFlag;cNode(){RootLength = 0;LeafLength = -1;LeafFlag = false;}}Node[MAX_N];void Input(){cin >> N;for (int i = 0; i < N - 1; i++){int x, y;cin >> x >> y;Edge[x].push_back(y);Edge[y].push_back(x);}}void RootToLeaf(int pos, int pre, int len){Node[pos].RootLength = len;bool leafFlag = true;for (int i = 0; i < Edge[pos].size(); i++){if (Edge[pos][i] == pre)continue;leafFlag = false;RootToLeaf(Edge[pos][i], pos, len + 1);}if (leafFlag){Node[pos].LeafFlag = true;}}void Calc(){//各ノードについて根からの距離を求める//ついでに葉かどうかも調べるRootToLeaf(1, -1, 0);//直近の葉からの距離を幅優先で調べるtypedef pair<int, int> II;queue<II> que;for (int i = 1; i <= N; i++){if (Node[i].LeafFlag)que.push(II(i, 0));}while (que.size()){II p = que.front();que.pop();int pos = p.first;int len = p.second;if (Node[pos].LeafLength >= 0)continue;Node[pos].LeafLength = len;for (int i = 0; i < Edge[pos].size(); i++){if (Node[Edge[pos][i]].LeafLength == -1){que.push(II(Edge[pos][i], len + 1));}}}}void Solve(){for (int i = 1; i <= N; i++){cout << min(Node[i].RootLength, Node[i].LeafLength) << endl;}}int main(){Input();Calc();Solve();return 0;}