結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-09-06 23:46:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 213 ms / 3,000 ms |
コード長 | 1,351 bytes |
コンパイル時間 | 1,936 ms |
コンパイル使用メモリ | 169,816 KB |
実行使用メモリ | 14,548 KB |
最終ジャッジ日時 | 2024-07-19 04:45:48 |
合計ジャッジ時間 | 5,096 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef vector<int> vi;typedef pair<int,int> ii;vector<vi> adjList;int rez[100001];int rez2[100001];bool passed[100001];void dfs(int cur,int d){if(passed[cur])return;passed[cur]=true;rez[cur]=min(d,rez2[cur]);for(int ctr1=0;ctr1<adjList[cur].size();ctr1++){dfs(adjList[cur][ctr1],rez[cur]+1);}}int main(){memset(passed,false,sizeof(passed));int n;cin>>n;for(int ctr1=0;ctr1<n;ctr1++){vi t;adjList.push_back(t);rez[ctr1]=9999999;}for(int ctr1=0;ctr1<n-1;ctr1++){int x,y;cin>>x>>y;x--;y--;adjList[x].push_back(y);adjList[y].push_back(x);}queue<ii> kju;for(int ctr1=0;ctr1<n;ctr1++)if(adjList[ctr1].size()==1)kju.push(make_pair(ctr1,0));while(!kju.empty()){ii t=kju.front();kju.pop();if(passed[t.first])continue;passed[t.first]=true;rez2[t.first]=t.second;for(int ctr1=0;ctr1<adjList[t.first].size();ctr1++)kju.push(make_pair(adjList[t.first][ctr1],t.second+1));}memset(passed,false,sizeof(passed));dfs(0,0);for(int ctr1=0;ctr1<n;ctr1++)cout<<min(rez[ctr1],rez2[ctr1])<<endl;return 0;}