結果
問題 | 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; }