結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2016-07-11 20:52:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 56 ms / 3,000 ms |
コード長 | 1,480 bytes |
コンパイル時間 | 456 ms |
コンパイル使用メモリ | 47,744 KB |
実行使用メモリ | 11,632 KB |
最終ジャッジ日時 | 2024-10-13 11:24:27 |
合計ジャッジ時間 | 2,044 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:65:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%d%d", &x[i], &y[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio>#include <cstring>#include <vector>#include <utility>#include <queue>using namespace std;typedef pair<int, int> P;const int kMAX_N = 100010;int dim[kMAX_N];int x[kMAX_N - 1], y[kMAX_N - 1];int R[kMAX_N], L[kMAX_N];int N;vector<int> graph[kMAX_N];void BFS(int start, int init, int cost[]) {fill(cost, cost + kMAX_N, -1);queue<P> que; // (頂点, 距離)cost[start] = init;que.push(P(start, init));while (!que.empty()) {P node = que.front(); que.pop();for (int i = 0; i < graph[node.first].size(); i++) {int to = graph[node.first][i];if (cost[to] < 0) {cost[to] = node.second + 1;que.push(P(to, cost[to]));}}}}void Solve() {for (int i = 0; i < N - 1; i++) {graph[x[i] - 1].push_back(y[i] - 1);graph[y[i] - 1].push_back(x[i] - 1);dim[x[i] - 1]++; dim[y[i] - 1]++;}int stab = N;for (int i = 0; i < N; i++) {if (i != 0 && dim[i] == 1) { // 葉graph[i].push_back(stab);graph[stab].push_back(i);}}// 根とスタブから幅優先BFS(0, 0, R);BFS(stab, -1, L);for (int i = 0; i < N; i++) {printf("%d\n", min(R[i], L[i]));}}int main() {scanf("%d", &N);for (int i = 0; i < N - 1; i++) {scanf("%d%d", &x[i], &y[i]);}Solve();return 0;}