結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-05 01:19:52 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,681 bytes |
コンパイル時間 | 817 ms |
コンパイル使用メモリ | 87,048 KB |
実行使用メモリ | 10,680 KB |
最終ジャッジ日時 | 2024-07-19 03:01:35 |
合計ジャッジ時間 | 6,553 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 18 |
コンパイルメッセージ
main.cpp: In function ‘int dfs(int, int, int)’: main.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type] 49 | } | ^
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <queue>#include <stack>#include <set>#include <map>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <numeric>#include <bitset>#include <complex>#define rep(x, to) for (int x = 0; x < (to); x++)#define REP(x, a, to) for (int x = (a); x < (to); x++)#define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++)#define EPS (1e-14)using namespace std;typedef long long ll;typedef pair<int, int> PII;typedef pair<ll, ll> PLL;typedef complex<double> Complex;typedef vector< vector<int> > Mat;queue<int> Q;const int INF = (int)(1e+9 + 7);const int MAX_V = 100005;int N;int L[MAX_V], R[MAX_V];bool leaf[MAX_V];vector<int> edge[MAX_V];int dfs(int u, int prev, int depth) {if (prev == -1 && edge[u].size() == 1) leaf[u] = true;R[u] = depth;bool is_leaf = true;rep(i, edge[u].size()) {int v = edge[u][i];if (v == prev) continue;dfs(v, u, depth + 1);is_leaf = false;}if (is_leaf) leaf[u] = true;}void bfs() {memset(L, -1, sizeof(R));rep(i, N) {if (!leaf[i + 1]) continue;Q.push(i + 1);L[i + 1] = 0;}while (!Q.empty()) {int u = Q.front(); Q.pop();rep(i, edge[u].size()) {int v = edge[u][i];if (L[v] != -1) continue;L[v] = L[u] + 1;Q.push(v);}}}void solve() {dfs(1, -1, 0);bfs();rep(i, N) {cout << min(R[i + 1], L[i + 1]) << endl;//cout << R[i + 1] << " " << L[i + 1] << endl;}}int main() {cin >> N;rep(i, N - 1) {int x, y;cin>> x >> y;edge[x].push_back(y);edge[y].push_back(x);}solve();return 0;}