結果

問題 No.277 根掘り葉掘り
ユーザー motimoti
提出日時 2015-10-22 22:34:31
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 198 ms / 3,000 ms
コード長 1,272 bytes
コンパイル時間 1,068 ms
コンパイル使用メモリ 110,296 KB
実行使用メモリ 10,628 KB
最終ジャッジ日時 2024-07-22 23:00:17
合計ジャッジ時間 4,152 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
int N;
vector<int> tree[100001];
vector<int> deg;
int dist[100001];
void bfs() {
rep(i, N) dist[i] = 1e9;
queue<pair<int, int>> q;
vector<bool> vis(N);
q.emplace(0, 0);
vis[0] = 1;
dist[0] = 0;
rep(i, N) {
if(deg[i] == 1) q.emplace(i, 0), dist[i] = 0, vis[i] = 1;
}
while(!q.empty()) {
auto p = q.front(); q.pop();
dist[p.first] = min(dist[p.first], p.second);
rep(i, tree[p.first].size()) {
int tar = tree[p.first][i];
if(vis[tar]) { continue; }
vis[tar] = 1;
q.emplace(tar, p.second+1);
}
}
}
int main() {
cin >> N;
deg.resize(N);
rep(i, N-1) {
int x, y; cin >> x >> y;
x--, y--;
deg[x]++, deg[y]++;
tree[x].push_back(y);
tree[y].push_back(x);
}
bfs();
rep(i, N) cout << dist[i] << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0