結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-05 11:54:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 227 ms / 3,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 782 ms |
コンパイル使用メモリ | 96,060 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-07-19 03:48:22 |
合計ジャッジ時間 | 4,339 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <map>#include <set>#include <list>#include <cmath>#include <queue>#include <stack>#include <cstdio>#include <string>#include <vector>#include <complex>#include <cstdlib>#include <cstring>#include <numeric>#include <sstream>#include <algorithm>#include <functional>#include <limits.h>#include <bitset>#include <tuple>#include <unordered_map>#define mp make_pair#define mt make_tuple#define pb push_back#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> pii;const int INF=1<<29;const double EPS=1e-9;const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};int N;vector<int> graph[100010];queue<pii> que;int from_child[100010];int from_root[100010];int main(){cin >> N;for (int i = 0; i < N - 1; i++){int a,b;cin >> a >> b;a--,b--;graph[a].push_back(b);graph[b].push_back(a);}vector<int> child;for (int i = 0; i < N; i++){if (graph[i].size() == 1){que.push(mp(i, 0));}}memset(from_child, -1, sizeof(from_child));while (!que.empty()){pii pos = que.front();que.pop();if (from_child[pos.first] != -1)continue;from_child[pos.first] = pos.second;for (int i = 0; i < graph[pos.first].size(); i++){que.push(mp(graph[pos.first][i], pos.second + 1));}}while (!que.empty())que.pop();memset(from_root, -1, sizeof(from_root));que.push(mp(0, 0));while (!que.empty()){pii pos = que.front();que.pop();if (from_root[pos.first] != -1)continue;from_root[pos.first] = pos.second;for (int i = 0; i < graph[pos.first].size(); i++){que.push(mp(graph[pos.first][i], pos.second + 1));}}for (int i = 0; i < N; i++){cout << min(from_child[i], from_root[i]) << endl;}return 0;}