結果
問題 | No.317 辺の追加 |
ユーザー | 37zigen |
提出日時 | 2016-03-24 19:07:54 |
言語 | Java21 (openjdk 21) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,356 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 753,636 KB |
最終ジャッジ日時 | 2024-10-02 00:14:04 |
合計ジャッジ時間 | 6,626 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 135 ms
47,036 KB |
testcase_01 | AC | 123 ms
40,660 KB |
testcase_02 | MLE | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
ソースコード
package yukicoder317; import java.util.ArrayList; import java.util.Arrays; import java.util.Date; import java.util.Scanner; public class Main { static class UnionFind{ static int[] data; UnionFind(int size){ data=new int[size]; Arrays.fill(data, -1); } boolean unionSet(int x,int y){ x=root(x); y=root(y); if(x!=y){ if(data[y]<data[x]){ int tmp=x; x=y; y=tmp; } data[x]+=data[y]; data[y]=x; } return x!=y; } boolean findSet(int x,int y){ return root(x)==root(y); } int root(int x){ return data[x]<0?x:root(data[x]); } int size(int x){ return -data[root(x)]; } } public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); UnionFind uf=new UnionFind(n+1); for(int i=0;i<m;i++){ uf.unionSet(sc.nextInt(), sc.nextInt()); } double t=new Date().getTime(); int[] d=new int[n+1]; int[][] nodes=new int[n+1][1000]; for(int i=0;i<n+1;i++){ for(int j=0;j<1000;j++){ nodes[i][j]=0; } } Arrays.fill(d,-1); ArrayList<Integer> list=new ArrayList<>(); int[][] cost=new int[n+1][1000]; for(int i=0;i<n+1;i++){ for(int j=0;j<1000;j++){ cost[i][j]=0; } } for(int i=1;i<=n;i++){ if(!list.contains(uf.root(i))){ list.add(uf.root(i)); nodes[uf.size(i)][0]++; cost[uf.size(i)][0]=1; } } for(int s=0;s<1000;s++){ for(int i=1;i<=n;i++){ if(nodes[i][s]==0)continue; int count=1; int num=nodes[i][s];//nodes=100=1+2+4+8+16+21+ int sum=1; if(nodes[i][s]>1){ if(sum+Math.pow(2, count)<=num){ cost[(int)Math.pow(2, count)*i][(int)Math.pow(2, count)-1]+=(int)Math.pow(2, count); nodes[i][s]-=(int)Math.pow(2, count); sum+=Math.pow(2, count); }else if(sum+Math.pow(2, count)>num){ cost[nodes[i][s]*i][nodes[i][s]-1]=nodes[i][s]; nodes[i][s]=0; } count++; } for(int j=0;j<nodes[i][s];j++){ for(int k=n;k-i>=0;k--){ if(k-i==0){ d[k]=0; continue; }else if(d[k-i]!=-1){ if(d[k]!=-1){ d[k]=Math.min(d[k], d[k-i]+cost[i][s]); }else if(d[k]==-1){ d[k]=d[k-i]+cost[i][s]; } } } } } } for(int i=1;i<=n;i++){ System.out.println(d[i]); } System.err.println(new Date().getTime()-t+"ms"); } }