Submission #2434744


Source Code Expand

import java.awt.RadialGradientPaint;
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        try (PrintWriter writer = new PrintWriter(System.out); InputReader reader = new InputReader(System.in)) {
            int[] input = reader.readIntsSplitByDelimiter(" ");
            int numOfMember = input[0];
            int numOfRelation = input[1];

            List<Relation> relationList = new ArrayList<>(numOfRelation);
            for (int i = 0; i < numOfRelation; i++) {
                int[] r = reader.readIntsSplitByDelimiter(" ");
                Relation relation = new Relation(r[0] - 1, r[1] - 1);
                relationList.add(relation);
            }

            int max = 0;
            for (int i = 1; i < (1 << numOfMember); i++) {
                if (canMakeGroup(i, numOfMember, relationList)) {
                    char[] a = Integer.toBinaryString(i).toCharArray();
                    int count  = 0;
                    for (char ac : a) {
                        if (ac == '1') {
                            count++;
                        }
                    }

                    max = Math.max(max, count);
                }
            }

            System.out.println(max);
        }
    }

    static boolean canMakeGroup(int bitPattern, int numOfMember, List<Relation> relationList) {
        for (int j = 0; j < numOfMember; j++) {
            if ((bitPattern & (1 << j)) == 0) {
                continue;
            }

            for (int k = j + 1; k < numOfMember; k++) {
                if ((bitPattern & (1 << k)) == 0) {
                    continue;
                }

                if (!haveRelation(j, k, relationList)) {
                    return false;
                }
            }
        }

        return true;
    }

    static boolean haveRelation(int i, int j, List<Relation> list) {
        for (Relation r : list) {
            if (r.getMember1() == i && r.getMember2() == j) {
                return true;
            }
        }

        return false;
    }
}

class Relation {
    private final int member1;
    private final int member2;

    Relation(int member1, int member2) {
        this.member1 = member1;
        this.member2 = member2;
    }

    int getMember1() {
        return this.member1;
    }

    int getMember2() {
        return this.member2;
    }
}
 
class InputReader implements Closeable, AutoCloseable {
    private final BufferedReader br;
 
    InputReader(InputStream inputStream) {
        this.br = new BufferedReader(new InputStreamReader(inputStream));
    }
 
    String readLine() throws IOException {
        return this.br.readLine();
    }
 
    int readInt() throws IOException {
        return Integer.parseInt(this.br.readLine());
    }
 
    long readLong() throws IOException {
        return Long.parseLong(this.br.readLine());
    }
 
    String[] readStringsSplitByDelimiter(String delimiter) throws IOException {
        return this.br.readLine().split(delimiter);
    }
 
    int[] readIntsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.br.readLine().split(delimiter);
 
        int stringsLength = strings.length;
        int[] ints = new int[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            ints[i] = Integer.parseInt(strings[i]);
        }
 
        return ints;
    }
 
    long[] readLongsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.br.readLine().split(delimiter);
 
        int stringsLength = strings.length;
        long[] longs = new long[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            longs[i] = Long.parseLong(strings[i]);
        }
 
        return longs;
    }
 
    @Override
    public void close() throws IOException {
        br.close();
    }
}

Submission Info

Submission Time
Task D - 派閥
User mt_kuma
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 4259 Byte
Status AC
Exec Time 115 ms
Memory 25940 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 74
Set Name Test Cases
all 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 72 ms 19156 KB
00_sample_02.txt AC 73 ms 20820 KB
00_sample_03.txt AC 73 ms 20948 KB
00_sample_04.txt AC 73 ms 17748 KB
test_01.txt AC 71 ms 18644 KB
test_02.txt AC 82 ms 21332 KB
test_03.txt AC 72 ms 19412 KB
test_04.txt AC 70 ms 17876 KB
test_05.txt AC 82 ms 19284 KB
test_06.txt AC 82 ms 19924 KB
test_07.txt AC 70 ms 19668 KB
test_08.txt AC 88 ms 21332 KB
test_09.txt AC 92 ms 18772 KB
test_10.txt AC 85 ms 18004 KB
test_11.txt AC 92 ms 19540 KB
test_12.txt AC 86 ms 19028 KB
test_13.txt AC 71 ms 18132 KB
test_14.txt AC 81 ms 19284 KB
test_15.txt AC 74 ms 18004 KB
test_16.txt AC 90 ms 18772 KB
test_17.txt AC 87 ms 19028 KB
test_18.txt AC 88 ms 19796 KB
test_19.txt AC 100 ms 21460 KB
test_20.txt AC 115 ms 23380 KB
test_21.txt AC 91 ms 21460 KB
test_22.txt AC 104 ms 24148 KB
test_23.txt AC 101 ms 21972 KB
test_24.txt AC 108 ms 22356 KB
test_25.txt AC 69 ms 19412 KB
test_26.txt AC 84 ms 18260 KB
test_27.txt AC 74 ms 19540 KB
test_28.txt AC 73 ms 19408 KB
test_29.txt AC 77 ms 20052 KB
test_30.txt AC 91 ms 18516 KB
test_31.txt AC 111 ms 25940 KB
test_32.txt AC 88 ms 19924 KB
test_33.txt AC 103 ms 22100 KB
test_34.txt AC 84 ms 18644 KB
test_35.txt AC 103 ms 22996 KB
test_36.txt AC 107 ms 22100 KB
test_37.txt AC 90 ms 19668 KB
test_38.txt AC 115 ms 25556 KB
test_39.txt AC 101 ms 21972 KB
test_40.txt AC 87 ms 21076 KB
test_41.txt AC 105 ms 18644 KB
test_42.txt AC 108 ms 23380 KB
test_43.txt AC 92 ms 21716 KB
test_44.txt AC 98 ms 20948 KB
test_45.txt AC 100 ms 19540 KB
test_46.txt AC 104 ms 21968 KB
test_47.txt AC 102 ms 21972 KB
test_48.txt AC 109 ms 22100 KB
test_49.txt AC 84 ms 18772 KB
test_50.txt AC 90 ms 23252 KB
test_51.txt AC 98 ms 21844 KB
test_52.txt AC 85 ms 18388 KB
test_53.txt AC 84 ms 18516 KB
test_54.txt AC 87 ms 19668 KB
test_55.txt AC 100 ms 19156 KB
test_56.txt AC 89 ms 18772 KB
test_57.txt AC 86 ms 20436 KB
test_58.txt AC 102 ms 24148 KB
test_59.txt AC 104 ms 23124 KB
test_60.txt AC 110 ms 24148 KB
test_61.txt AC 107 ms 21844 KB
test_62.txt AC 71 ms 19284 KB
test_63.txt AC 95 ms 19156 KB
test_64.txt AC 84 ms 21844 KB
test_65.txt AC 86 ms 21716 KB
test_66.txt AC 93 ms 18516 KB
test_67.txt AC 87 ms 19796 KB
test_68.txt AC 86 ms 21844 KB
test_69.txt AC 86 ms 19284 KB
test_70.txt AC 87 ms 19924 KB