結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-04 22:35:47 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 220 ms / 3,000 ms |
コード長 | 630 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 163,872 KB |
実行使用メモリ | 10,112 KB |
最終ジャッジ日時 | 2024-07-19 00:58:12 |
合計ジャッジ時間 | 4,605 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;int cost[100010];vector<int> g[100010];int deg[100010];int main(){memset(cost,-1,sizeof(cost));int n;cin >> n;queue<int> Q;for(int i = 1 ; i < n ; i++){int a,b;cin >> a >> b;--a,--b;g[a].push_back(b);g[b].push_back(a);deg[a]++;deg[b]++;}for(int i = 0 ; i < n ; i++){if( i == 0 || deg[i] == 1 ){Q.push(i);cost[i] = 0;}}while(Q.size()){int q = Q.front(); Q.pop();for( auto e : g[q] ){if( cost[e] == -1 ){cost[e] = cost[q] + 1;Q.push(e);}}}for(int i = 0 ; i < n ; i++)cout << cost[i] << endl;}