結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2021-02-15 21:30:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 3,000 ms |
コード長 | 1,320 bytes |
コンパイル時間 | 1,045 ms |
コンパイル使用メモリ | 103,396 KB |
実行使用メモリ | 10,364 KB |
最終ジャッジ日時 | 2024-07-23 13:11:55 |
合計ジャッジ時間 | 5,461 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;bool bo[100010] = { false };int r[100010], l[100010];vector<vector<int>> vec(100010);int main() {int n;cin >> n;for (int i = 0; i < n - 1; i++) {int x, y;cin >> x >> y;vec[x].emplace_back(y);vec[y].emplace_back(x);}queue<int> que, que1;que.push(1);for (int i = 1; i <= n; i++) {r[i] = 1000000007, l[i] = 1000000007;}r[1] = 0;bo[1] = true;while (!que.empty()) {int now = que.front();que.pop();bool qb = true;for (int i = 0; i < vec[now].size(); i++) {if (!bo[vec[now][i]]) {bo[vec[now][i]] = true;qb = false;}if (r[vec[now][i]] > r[now] + 1) {r[vec[now][i]] = r[now] + 1;que.push(vec[now][i]);}}if (qb) {l[now] = 0;que1.push(now);}}while (!que1.empty()) {int now = que1.front();que1.pop();for (int i = 0; i < vec[now].size(); i++) {if (l[vec[now][i]] > l[now] + 1) {l[vec[now][i]] = l[now] + 1;que1.push(vec[now][i]);}}}for (int i = 1; i <= n; i++) {cout << min(r[i], l[i]) << endl;}}