結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-07 13:40:07 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 225 ms / 3,000 ms |
コード長 | 1,974 bytes |
コンパイル時間 | 668 ms |
コンパイル使用メモリ | 77,348 KB |
実行使用メモリ | 11,260 KB |
最終ジャッジ日時 | 2024-07-19 04:53:11 |
合計ジャッジ時間 | 4,265 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <cstring>#include <algorithm>#include <sstream>#include <map>#include <set>#include <queue>#define REP(i,k,n) for(int i=k;i<n;i++)#define rep(i,n) for(int i=0;i<n;i++)#define INF 1<<30#define pb push_back#define mp make_pairusing namespace std;typedef long long ll;typedef pair<int,int> P;int n;vector<int> G[100005];int d[100005],d2[100005];bool used[100005],inQ[100005];int main() {cin >> n;rep(i,n-1) {int s,t;cin >> s >> t;s--;t--;G[s].push_back(t);G[t].push_back(s);}queue<P> que;que.push(P(0,0));memset(used,0,sizeof(used));used[0] = true;memset(d,0,sizeof(d));while(que.size()) {P p = que.front();que.pop();int now = p.first;int cnt = p.second;rep(i,G[now].size()) {int next = G[now][i];if(!used[next]) {used[next] = true;d[next] = cnt+1;que.push(P(next,cnt+1));}}}vector<int> leaf;rep(i,n) {if(G[i].size() == 1) {leaf.push_back(i);}}memset(inQ,0,sizeof(inQ));memset(used,0,sizeof(used));memset(d2,0,sizeof(d2));rep(i,leaf.size()) {inQ[leaf[i]] = true;used[leaf[i]] = true;que.push(P(leaf[i],0));}while(que.size()) {P p = que.front();que.pop();inQ[p.first] = false;int now = p.first;int cnt = p.second;rep(i,G[now].size()) {int next = G[now][i];if(!used[next] && !inQ[next]) {used[next] = true;inQ[next] = true;d2[next] = cnt+1;que.push(P(next,cnt+1));}}}rep(i,n) {cout << min(d[i],d2[i]) << endl;}return 0;}