結果
問題 | No.386 貪欲な領主 |
ユーザー | kuuso1 |
提出日時 | 2016-07-02 22:41:55 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 5,527 bytes |
コンパイル時間 | 980 ms |
コンパイル使用メモリ | 116,752 KB |
実行使用メモリ | 43,896 KB |
最終ジャッジ日時 | 2024-04-20 21:31:18 |
合計ジャッジ時間 | 3,222 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
17,536 KB |
testcase_01 | AC | 24 ms
17,664 KB |
testcase_02 | AC | 25 ms
17,920 KB |
testcase_03 | AC | 24 ms
17,664 KB |
testcase_04 | AC | 208 ms
42,864 KB |
testcase_05 | AC | 219 ms
43,896 KB |
testcase_06 | AC | 222 ms
43,388 KB |
testcase_07 | AC | 25 ms
17,536 KB |
testcase_08 | AC | 40 ms
19,624 KB |
testcase_09 | AC | 24 ms
17,664 KB |
testcase_10 | AC | 23 ms
17,536 KB |
testcase_11 | AC | 27 ms
17,792 KB |
testcase_12 | AC | 26 ms
17,536 KB |
testcase_13 | AC | 30 ms
18,432 KB |
testcase_14 | AC | 225 ms
43,884 KB |
testcase_15 | AC | 190 ms
42,736 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ using(var r = new FastIn(100000)){ N=r.ReadInt(); E=new List<int>[N]; for(int i=0;i<N;i++)E[i]=new List<int>(); for(int i=0;i<N-1;i++){ int[] d = new int[2]; d[0] = r.ReadInt(); d[1] = r.ReadInt(); E[d[0]].Add(d[1]); E[d[1]].Add(d[0]); } U = new long[N]; for(int i=0;i<N;i++){ U[i] = r.ReadLong(); } LCAInit(); M =r.ReadInt(); long[] sum = new long[N]; for(int i=0;i<N;i++)sum[i] = U[i]; Queue<int> Q = new Queue<int>(); Q.Enqueue(root); while(Q.Count>0){ var now = Q.Dequeue(); foreach(var nxt in E[now]){ if(nxt == parent[0][now])continue; sum[nxt] += sum[now]; Q.Enqueue(nxt); } } long ans = 0; int from,to; long w; for(;M>0;M--){ from = r.ReadInt(); to = r.ReadInt(); w = r.ReadLong(); var p = lca(from,to); long weight = w * (sum[from] + sum[to] - 2*sum[p] + U[p]); ans += weight; } Console.WriteLine(ans); } } public Sol(){ } int M; long[] U; int N; List<int>[] E; int[][] parent; int[] depth; static int lmax=24; int root; int lca(int u,int v){ if(depth[u]>depth[v])return lca(v,u); for(int i=0;i<lmax;i++){ if( (((depth[v]-depth[u])>>i)&1) >0 ){ v=parent[i][v]; } } if(u==v)return u; for(int i=lmax-1;i>=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } return parent[0][u]; } void LCAInit(){ parent=new int[lmax][]; for(int i=0;i<lmax;i++){ parent[i]=new int[N]; } depth=new int[N]; root=0; //dfs(root,-1,0);//深さを数えるdfs bfs(root,0);//深さを数えるbfs for(int i=0;i<lmax-1;i++){ for(int j=0;j<N;j++){ if(parent[i][j]<0){ parent[i+1][j]=-1; }else{ parent[i+1][j]=parent[i][parent[i][j]]; } } } } void dfs(int now,int par,int dep){ parent[0][now]=par; depth[now]=dep; foreach(int v in E[now]){ if(v!=par){ dfs(v,now,dep+1); } } } void bfs(int strt,int dep_strt){ Queue<int> Q=new Queue<int>(); parent[0][strt]=-1;depth[strt]=0; Q.Enqueue(strt); while(Q.Count>0){ int now=Q.Dequeue(); int par=parent[0][now]; foreach(int v in E[now]){ if(v!=par){ parent[0][v]=now;depth[v]=depth[now]+1; Q.Enqueue(v); } } } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } class FastIn:IDisposable { int Size; byte[] Mem; int ptr; int rsize; bool unfinished; Stream stdin; void Init(int n) { Size = n; Mem = new byte[Size]; rsize=(stdin=Console.OpenStandardInput()).Read(Mem, 0, Size); ptr = 0; unfinished=(rsize == Size); } void Next() { if (unfinished == false) return; rsize=stdin.Read(Mem, 0, Size); ptr = 0; unfinished = (rsize == Size); } ~FastIn(){ stdin.Dispose(); } void IDisposable.Dispose(){ stdin.Dispose(); } public void Dispose(){ stdin.Dispose(); } public FastIn() { Init(100000); } public FastIn(int n) { Init(n); } public int ReadInt() { int ret = 0; int sig = 1; while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) { if(ret==0 && Mem[ptr] == '-'){ sig *= -1; ptr++; continue; } ret = ret * 10 + Mem[ptr++] - '0'; if (ptr == Size) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size) Next(); } return ret*sig; } public long ReadLong() { long ret = 0; long sig = 1; while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) { if(ret==0 && Mem[ptr] == '-'){ sig *= -1; ptr++; continue; } ret = ret * 10 + Mem[ptr++] - '0'; if (ptr == Size) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size) Next(); } return ret*sig; } public String ReadStr() { //2byte文字はNG StringBuilder sb = new StringBuilder(); while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r') { sb.Append((char)Mem[ptr++]); if (ptr == Size && unfinished) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size && unfinished) Next(); } return sb.ToString(); } public String ReadLine() { //極力使わない(split/parseするくらいなら上をつかう) StringBuilder sb = new StringBuilder(); while (ptr < rsize && Mem[ptr] != '\n' && Mem[ptr] != '\r') { sb.Append((char)Mem[ptr++]); if (ptr == Size && unfinished) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')) { ptr++; if (ptr == Size && unfinished) Next(); } return sb.ToString(); } }