Submission #1151830
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ public Solve(){} StringBuilder sb; public static int Main(){ new Solve().Run(); return 0; } void Run(){ sb = new StringBuilder(); Calc(); Console.Write(sb.ToString()); } void Calc(){ int N = int.Parse(Console.ReadLine()); int[] a = new int[N]; int[] b = new int[N]; List<int>[] G = new List<int>[N]; for(int i=0;i<N;i++){ G[i] = new List<int>(); } for(int i=0;i<N-1;i++){ string[] str = Console.ReadLine().Split(' '); a[i] = int.Parse(str[0])-1; b[i] = int.Parse(str[1])-1; G[a[i]].Add(b[i]); G[b[i]].Add(a[i]); } string s = Console.ReadLine(); int o = 0; for(int i=0;i<N;i++){ if(s[i] == '1'){ o++; } } int[] depth; int[] depth2; int[] depth3; int[] depthR; int[] depthv; int[] child; { Tree T = new Tree(G,s); depth = T.GetDepth(0); T.GetDepthR(0); depth2 = T.depth2; depth3 = T.depth3; depthR = T.depthR; depthv = T.depthv; child = T.GetDecendant(0); } long count = 0; for(int i=0;i<N;i++){ int min = N+1; int max = 0; if(s[i] == '1'){ min = 0; } else{ for(int j=0;j<G[i].Count;j++){ int t = G[i][j]; if(depth[t] > depth[i]){ if(child[t] > 0){ min = Math.Min(min,depth2[t]); } } else if(depthv[t] == i){ if(o - child[i] > 0){ min = Math.Min(min,Math.Max(depth3[t],depthR[t])); } } else{ if(o - child[i] > 0){ min = Math.Min(min,Math.Max(depth2[t],depthR[t])); } } } } max = (depthR[i] > depth3[i] ? Math.Min(depth2[i],depthR[i]) : depth3[i]) - 1; count += Math.Max(max - min + 1,0); } for(int i=0;i<N-1;i++){ int p1,p2; if(depth[a[i]] > depth[b[i]]){ p1 = b[i]; p2 = a[i]; } else{ p1 = a[i]; p2 = b[i]; } int d1 = depthv[p1] == p2 ? Math.Max(depth3[p1],depthR[p1]) : Math.Max(depth2[p1],depthR[p1]); int d2 = depth2[p2]; if(d1 == d2 || (d1 > d2 && child[p2] > 0) || (d2 > d1 && o > child[p2])){ count++; } } sb.Append(count+"\n"); } } public class Tree{ List<int>[] T; bool[] b; int N; int temp1; int temp2; int[] depth; int[] parent; int[] decendant; string s; public int[] depth2; public int[] depthv; public int[] depth3; public int[] depthR; public int center1; public int center2; public int diamater; public Tree(List<int>[] G,string s0){ T = G; N = G.Length; s = s0; } void calcLongestPath(int v){ b = new bool[N]; temp1 = 0; temp2 = 0; dfs1(v,0); } public int LongestPathDistance(int v){ calcLongestPath(v); return temp1; } public int LongestPath(int v){ calcLongestPath(v); return temp2; } public void Diamater(){ int x1 = LongestPath(0); int x2 = LongestPath(x1); diamater = temp1; } public void Center(){ int x1 = LongestPath(0); int x2 = LongestPath(x1); diamater = temp1; if(diamater % 2 == 0){ center1 = Search(x1,x2,diamater/2); center2 = -1; } else{ center1 = Search(x1,x2,diamater/2); center2 = Search(x1,x2,diamater/2+1); } } public int Search(int s,int t,int l){ b = new bool[N]; dfs2(s,t,0,l); return temp1; } //上から何番目か public int[] GetDepth(int p){ b = new bool[N]; depth = new int[N]; dfs3(p,0); return depth; } public int[] GetParent(int p){ b = new bool[N]; parent = new int[N]; dfs4(p,-1); return parent; } public int[] GetDecendant(int p){ b = new bool[N]; decendant = new int[N]; dfs5(p); return decendant; } //子孫の深さ public int[] GetDepth2(int p){ b = new bool[N]; depth2 = new int[N]; dfs6(p); return depth2; } //2番目まで public void GetDepth3(int p){ b = new bool[N]; depth2 = new int[N]; depthv = new int[N]; depth3 = new int[N]; dfs7(p); } public int[] GetDepthR(int p){ GetDepth3(p); b = new bool[N]; depthR = new int[N]; dfs8(p,0); return depthR; } void dfs1(int v,int l){ b[v] = true; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ dfs1(t,l+1); } } if(l >= temp1){ temp1 = l; temp2 = v; } } bool dfs2(int v,int o,int l,int d){ b[v] = true; bool x = v == o; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ x |= dfs2(t,o,l+1,d); } } if(x && l == d){ temp1 = v; } return x; } void dfs3(int v,int d){ b[v] = true; depth[v] = d; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ dfs3(t,d+1); } } } void dfs4(int v,int p){ b[v] = true; parent[v] = p; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ dfs4(t,v); } } } int dfs5(int v){ b[v] = true; int count = s[v] == '1' ? 1 : 0; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ count += dfs5(t); } } decendant[v] = count; return count; } int dfs6(int v){ b[v] = true; int count = 1; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ count = Math.Max(count,dfs6(t)+1); } } depth2[v] = count; return count; } int dfs7(int v){ b[v] = true; int m = 1; int m2 = 1; int mv = -1; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ int c = dfs7(t) + 1; if(c > m){ m2 = m; m = c; mv = t; } else if(c > m2){ m2 = c; } } } depth2[v] = m; depth3[v] = m2; depthv[v] = mv; return m; } void dfs8(int v,int d){ b[v] = true; depthR[v] = d+1; for(int i=0;i<T[v].Count;i++){ int t = T[v][i]; if(!b[t]){ int td = depthv[v] == t ? Math.Max(depth3[v],d+1) : Math.Max(depth2[v],d+1); dfs8(t,td); } } } }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | leign |
Language | C# (Mono 4.6.2.0) |
Score | 1900 |
Code Size | 8111 Byte |
Status | AC |
Exec Time | 593 ms |
Memory | 54236 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | 600 / 600 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt |
Subtask | 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 22 ms | 9172 KB |
0_01.txt | AC | 22 ms | 11220 KB |
0_02.txt | AC | 22 ms | 11220 KB |
1_00.txt | AC | 23 ms | 11220 KB |
1_01.txt | AC | 527 ms | 52032 KB |
1_02.txt | AC | 514 ms | 47808 KB |
1_03.txt | AC | 481 ms | 40256 KB |
1_04.txt | AC | 445 ms | 40896 KB |
1_05.txt | AC | 379 ms | 47300 KB |
1_06.txt | AC | 464 ms | 40768 KB |
1_07.txt | AC | 497 ms | 44864 KB |
1_08.txt | AC | 474 ms | 45760 KB |
1_09.txt | AC | 488 ms | 48192 KB |
1_10.txt | AC | 484 ms | 49208 KB |
1_11.txt | AC | 498 ms | 51504 KB |
1_12.txt | AC | 465 ms | 44336 KB |
1_13.txt | AC | 490 ms | 49744 KB |
1_14.txt | AC | 476 ms | 46736 KB |
1_15.txt | AC | 467 ms | 43872 KB |
1_16.txt | AC | 479 ms | 45552 KB |
1_17.txt | AC | 510 ms | 46920 KB |
1_18.txt | AC | 503 ms | 46220 KB |
1_19.txt | AC | 496 ms | 42252 KB |
1_20.txt | AC | 538 ms | 39856 KB |
1_21.txt | AC | 536 ms | 43076 KB |
1_22.txt | AC | 481 ms | 46696 KB |
1_23.txt | AC | 471 ms | 40688 KB |
1_24.txt | AC | 501 ms | 41472 KB |
1_25.txt | AC | 474 ms | 42960 KB |
1_26.txt | AC | 456 ms | 39936 KB |
1_27.txt | AC | 447 ms | 43252 KB |
1_28.txt | AC | 453 ms | 41460 KB |
1_29.txt | AC | 473 ms | 43232 KB |
2_00.txt | AC | 22 ms | 9172 KB |
2_01.txt | AC | 593 ms | 53568 KB |
2_02.txt | AC | 557 ms | 51776 KB |
2_03.txt | AC | 553 ms | 51136 KB |
2_04.txt | AC | 563 ms | 47936 KB |
2_05.txt | AC | 569 ms | 46144 KB |
2_06.txt | AC | 548 ms | 49088 KB |
2_07.txt | AC | 535 ms | 40256 KB |
2_08.txt | AC | 538 ms | 46400 KB |
2_09.txt | AC | 548 ms | 40256 KB |
2_10.txt | AC | 490 ms | 45120 KB |
2_11.txt | AC | 473 ms | 41024 KB |
2_12.txt | AC | 477 ms | 43072 KB |
2_13.txt | AC | 406 ms | 45504 KB |
2_14.txt | AC | 386 ms | 43332 KB |
2_15.txt | AC | 386 ms | 47428 KB |
2_16.txt | AC | 502 ms | 46912 KB |
2_17.txt | AC | 501 ms | 40768 KB |
2_18.txt | AC | 505 ms | 42816 KB |
2_19.txt | AC | 506 ms | 42816 KB |
2_20.txt | AC | 503 ms | 40768 KB |
2_21.txt | AC | 483 ms | 42816 KB |
2_22.txt | AC | 503 ms | 43712 KB |
2_23.txt | AC | 517 ms | 44200 KB |
2_24.txt | AC | 509 ms | 44096 KB |
2_25.txt | AC | 535 ms | 48704 KB |
2_26.txt | AC | 542 ms | 47424 KB |
2_27.txt | AC | 540 ms | 48576 KB |
2_28.txt | AC | 527 ms | 46960 KB |
2_29.txt | AC | 558 ms | 54236 KB |
2_30.txt | AC | 548 ms | 50544 KB |
2_31.txt | AC | 543 ms | 44888 KB |
2_32.txt | AC | 522 ms | 45124 KB |
2_33.txt | AC | 502 ms | 47184 KB |
2_34.txt | AC | 522 ms | 50616 KB |
2_35.txt | AC | 550 ms | 48724 KB |
2_36.txt | AC | 541 ms | 43916 KB |
2_37.txt | AC | 534 ms | 40184 KB |
2_38.txt | AC | 485 ms | 41360 KB |
2_39.txt | AC | 520 ms | 42336 KB |
2_40.txt | AC | 471 ms | 47324 KB |
2_41.txt | AC | 471 ms | 46604 KB |
2_42.txt | AC | 449 ms | 40384 KB |
2_43.txt | AC | 499 ms | 48072 KB |
2_44.txt | AC | 426 ms | 40612 KB |
2_45.txt | AC | 402 ms | 47084 KB |
2_46.txt | AC | 397 ms | 41204 KB |
2_47.txt | AC | 448 ms | 43916 KB |