結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2018-10-30 16:28:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 278 ms / 3,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 203,920 KB |
最終ジャッジ日時 | 2025-01-06 15:09:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = int64_t;using vi = vector<i64>;using vvi = vector<vi>;vvi adj;int main() {int n;cin >> n;adj = vvi(n);for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;a--;b--;adj[a].push_back(b);adj[b].push_back(a);}vi rootdist(n, 1e9);queue<int> que;que.push(0);rootdist[0] = 0;while (que.size()) {int t = que.front();que.pop();for (int s: adj[t]) {if (rootdist[s] > rootdist[t] + 1) {rootdist[s] = rootdist[t] + 1;que.push(s);}}}vi leafdist(n, 1e9);for (int i = 1; i < n; i++) {if (adj[i].size() == 1) {que.push(i);leafdist[i] = 0;}}while (que.size()) {int t = que.front();que.pop();for (int s: adj[t]) {if (leafdist[s] > leafdist[t] + 1) {leafdist[s] = leafdist[t] + 1;que.push(s);}}}for (int i = 0; i < n; i++) {cout << min(rootdist[i], leafdist[i]) << endl;}}