結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 long
using namespace std;
#define MAX_N 100005
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0