結果
問題 | No.277 根掘り葉掘り |
ユーザー | tjake |
提出日時 | 2015-12-18 04:34:44 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 220 ms / 3,000 ms |
コード長 | 2,185 bytes |
コンパイル時間 | 750 ms |
コンパイル使用メモリ | 76,860 KB |
実行使用メモリ | 16,076 KB |
最終ジャッジ日時 | 2023-10-14 13:49:13 |
合計ジャッジ時間 | 4,196 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,700 KB |
testcase_01 | AC | 3 ms
5,656 KB |
testcase_02 | AC | 3 ms
5,816 KB |
testcase_03 | AC | 3 ms
5,648 KB |
testcase_04 | AC | 3 ms
5,704 KB |
testcase_05 | AC | 3 ms
5,676 KB |
testcase_06 | AC | 3 ms
5,688 KB |
testcase_07 | AC | 3 ms
5,780 KB |
testcase_08 | AC | 3 ms
5,724 KB |
testcase_09 | AC | 220 ms
16,076 KB |
testcase_10 | AC | 186 ms
10,004 KB |
testcase_11 | AC | 205 ms
9,808 KB |
testcase_12 | AC | 208 ms
12,912 KB |
testcase_13 | AC | 211 ms
9,888 KB |
testcase_14 | AC | 206 ms
10,164 KB |
testcase_15 | AC | 214 ms
10,476 KB |
testcase_16 | AC | 205 ms
10,032 KB |
testcase_17 | AC | 203 ms
10,132 KB |
testcase_18 | AC | 205 ms
9,956 KB |
testcase_19 | AC | 208 ms
10,148 KB |
ソースコード
#include<iostream> #include<string> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include<functional> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; #define mind(a,b) (a>b?b:a) #define maxd(a,b) (a>b?a:b) #define absd(x) (x<0?-(x):x) #define pow2(x) ((x)*(x)) #define rep(i,n) for(int i=0; i<n; ++i) #define repr(i,n) for(int i=n-1; i>=0; --i) #define repl(i,s,n) for(int i=s; i<=n; ++i) #define replr(i,s,n) for(int i=n; i>=s; --i) #define repf(i,s,n,j) for(int i=s; i<=n; i+=j) #define repe(e,obj) for(auto e : obj) #define SP << " " << #define COL << " : " << #define COM << ", " << #define ARR << " -> " << #define PNT(STR) cout << STR << endl #define POS(X,Y) "(" << X << ", " << Y << ")" #define DEB(A) " (" << #A << ") " << A #define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl #define ALL(V) (V).begin(), (V).end() #define INF 1000000007 #define INFLL 10000000000000000007LL #define EPS 1e-9 typedef unsigned int uint; typedef unsigned long ulong; typedef unsigned long long ull; typedef long long ll; typedef long double ld; typedef pair<int, int> P; //typedef pair<ll, ll> P; typedef pair<P, int> PI; typedef pair<int, P> IP; typedef pair<P, P> PP; typedef priority_queue<P, vector<P>, greater<P> > pvqueue; #define N 100007 vector<int> g[N]; int n; int ans[N]; int dist[N]; vector<int> le; int dfs(int v, int c, int f) { int ret = N; if(g[v].size()==1 && g[v][0]==f) { le.push_back(v); ans[v] = 0; return 1; } rep(i, g[v].size()) { int t = g[v][i]; if(t == f) continue; int r = dfs(t, c+1, v); ret = mind(ret, r); } ans[v] = mind(c, ret); dist[v] = ret; return ret+1; } void d_dfs(int v, int f) { rep(i, g[v].size()) { int t = g[v][i]; if(t == f) continue; if(dist[v]+1 < dist[t]) { dist[t] = dist[v]+1; ans[t] = mind(ans[t], dist[t]); } d_dfs(t, v); } } int main() { cin >> n; rep(i, n-1) { int x, y; cin >> x >> y; --x; --y; g[x].push_back(y); g[y].push_back(x); } dfs(0, 0, -1); d_dfs(0, -1); rep(i, n) { cout << ans[i] << endl; } return 0; }