結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2016-05-06 20:31:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 156 ms / 3,000 ms |
コード長 | 1,549 bytes |
コンパイル時間 | 1,366 ms |
コンパイル使用メモリ | 166,132 KB |
実行使用メモリ | 9,744 KB |
最終ジャッジ日時 | 2024-10-05 10:12:04 |
合計ジャッジ時間 | 4,066 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class Inquisitive{public:void solve(void){int N;cin>>N;vector<vector<int>> tree(N);REP(i,N-1){int x, y;cin>>x>>y;--x, --y;tree[x].push_back(y);tree[y].push_back(x);}const int inf = (1<<30);vector<int> dist(N,inf);queue<int> Q;Q.push(0);REP(i,N){if (tree[i].size() == 1){// 葉自身は葉までの距離 0dist[i] = 0;Q.push(i);}}dist[0] = 0; // 根自身までは距離 0// わかっていないのは幹だけ。よって根と葉から bfs すればよいwhile (!Q.empty()){int u = Q.front();Q.pop();for (auto to : tree[u]){if (dist[to] > dist[u] + 1){dist[to] = dist[u]+1;Q.push(to);}}}REP(i,N)cout<<dist[i]<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new Inquisitive();obj->solve();delete obj;return 0;}#endif