結果

問題 No.277 根掘り葉掘り
ユーザー airisairis
提出日時 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 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0