結果

問題 No.945 YKC饅頭
ユーザー 37zigen37zigen
提出日時 2019-12-06 02:23:25
言語 Java21
(openjdk 21)
結果
RE  
実行時間 -
コード長 2,588 bytes
コンパイル時間 4,961 ms
コンパイル使用メモリ 85,212 KB
実行使用メモリ 61,788 KB
最終ジャッジ日時 2023-08-24 19:36:55
合計ジャッジ時間 17,215 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 159 ms
56,796 KB
testcase_01 AC 160 ms
56,688 KB
testcase_02 AC 216 ms
57,740 KB
testcase_03 AC 239 ms
59,744 KB
testcase_04 AC 195 ms
57,884 KB
testcase_05 AC 213 ms
58,004 KB
testcase_06 AC 219 ms
60,208 KB
testcase_07 AC 212 ms
60,216 KB
testcase_08 AC 176 ms
56,756 KB
testcase_09 AC 220 ms
60,992 KB
testcase_10 AC 218 ms
60,440 KB
testcase_11 AC 219 ms
59,432 KB
testcase_12 AC 214 ms
61,788 KB
testcase_13 AC 237 ms
60,032 KB
testcase_14 AC 235 ms
60,740 KB
testcase_15 AC 213 ms
60,064 KB
testcase_16 AC 208 ms
57,764 KB
testcase_17 AC 237 ms
60,696 KB
testcase_18 AC 228 ms
60,096 KB
testcase_19 AC 168 ms
57,204 KB
testcase_20 AC 211 ms
58,988 KB
testcase_21 AC 217 ms
58,488 KB
testcase_22 AC 240 ms
60,088 KB
testcase_23 AC 245 ms
60,960 KB
testcase_24 AC 244 ms
61,188 KB
testcase_25 AC 241 ms
60,096 KB
testcase_26 AC 242 ms
59,976 KB
testcase_27 AC 164 ms
56,504 KB
testcase_28 AC 160 ms
56,964 KB
testcase_29 AC 160 ms
57,032 KB
testcase_30 AC 159 ms
57,048 KB
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 RE -
testcase_65 RE -
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
testcase_69 RE -
testcase_70 RE -
testcase_71 RE -
testcase_72 RE -
testcase_73 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
    
    class DJSet{
        int n;
        int[] upper;
        int[] ma;
        int[] mi;
        int[] cols;
        
        public DJSet(int n){
            this.n=n;
            upper=new int[n];
            ma=new int[n];
            mi=new int[n];
            cols=new int[n];
            Arrays.fill(upper,-1);
            Arrays.fill(cols,-1);
            for(int i=0;i<n;++i){
                ma[i]=i;
                mi[i]=i;
            }
        }
        
        //[l,r)
        void paint(int l, int r, int col){
            if(l>=r)return;
            if(cols[l]!=-1){
                paint(ma[root(l)]+1,r,col);
            }else{
                cols[l]=col;
                paint(l+1,r,col);
            }
            setUnion(l,r-1);
        }
        
        boolean equiv(int a, int b){
            return root(a)==root(b);
        }
        
        int root(int x){
            return upper[x]<0?x:(upper[x]=root(upper[x]));
        }
        
        void setUnion(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return;
            if(upper[x]<upper[y]){
                x^=y;y^=x;x^=y;
            }
            upper[y]+=upper[x];
            upper[x]=y;
            ma[y]=Math.max(ma[y],ma[x]);
            mi[y]=Math.min(mi[y],mi[x]);
        }
    }
    
    void run() {
        Scanner sc = new Scanner(System.in);
        int N=sc.nextInt();
        int M=sc.nextInt();
        if(!(N<=1000&&M<=1000))throw new AssertionError();
        if(!(1<=N&&N<=2e5))throw new AssertionError();
        if(!(1<=M&&M<=2e5))throw new AssertionError();
        DJSet ds=new DJSet(N);
        for(int i=0;i<M;++i){
            int L=sc.nextInt();
            int R=sc.nextInt();
            if(!(1<=L&&L<=R&&R<=N))throw new AssertionError();
            --L;--R;
            String T=sc.next();
            int col=-1;
            if(T.equals("Y")){
                col=0;
            }else if(T.equals("K")){
                col=1;
            }else if(T.equals("C")){
                col=2;
            }else{
                throw new AssertionError();
            }
            ds.paint(L,R+1,col);
        }
        int[] cnt=new int[3];
        for(int i=0;i<N;++i){
            if(ds.cols[i]!=-1)
                cnt[ds.cols[i]]++;
        }
        System.out.println(cnt[0]+" "+cnt[1]+" "+cnt[2]);
    }
    
    void tr(Object...objects){
        System.out.println(Arrays.deepToString(objects));
    }
}
0