結果
問題 | No.277 根掘り葉掘り |
ユーザー | yuppe19 😺 |
提出日時 | 2015-09-10 16:14:39 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 61 ms / 3,000 ms |
コード長 | 1,049 bytes |
コンパイル時間 | 767 ms |
コンパイル使用メモリ | 73,624 KB |
実行使用メモリ | 9,664 KB |
最終ジャッジ日時 | 2023-09-26 10:25:34 |
合計ジャッジ時間 | 2,750 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,384 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 57 ms
8,788 KB |
testcase_10 | AC | 47 ms
9,664 KB |
testcase_11 | AC | 57 ms
9,228 KB |
testcase_12 | AC | 54 ms
8,984 KB |
testcase_13 | AC | 61 ms
9,484 KB |
testcase_14 | AC | 55 ms
9,308 KB |
testcase_15 | AC | 56 ms
9,068 KB |
testcase_16 | AC | 56 ms
9,268 KB |
testcase_17 | AC | 49 ms
9,328 KB |
testcase_18 | AC | 53 ms
9,092 KB |
testcase_19 | AC | 52 ms
9,424 KB |
ソースコード
#include <iostream> #include <algorithm> #include <queue> using namespace std; using i64 = long long; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n; public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}}; const int inf = 987654321; vector<vector<int>> G; int main(void) { int n; scanf("%d", &n); G.assign(n, vector<int>()); for(int i : range(n-1)) { int x, y; scanf("%d%d", &x, &y); x--, y--; G[x].push_back(y); G[y].push_back(x); } vector<int> dist(n, inf); dist[0] = 0; queue<int> que; que.push(0); for(int v : range(1, n)) { if(G[v].size() == 1) { dist[v] = 0; que.push(v); } } while(!que.empty()) { int v = que.front(); que.pop(); for(int vv : G[v]) { if(dist[vv] > dist[v] + 1) { dist[vv] = dist[v] + 1; que.push(vv); } } } for(int v : range(n)) { printf("%d\n", dist[v]); } return 0; }