Submission #2724080


Source Code Expand

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

public class Main {
    FastScanner in;
    PrintWriter out;

    int sum(int n) {
        return n < 10 ? n : (n % 10 + sum(n / 10));
    }

    int n;
    boolean[][] g;
    int[] color;
    int cnt0 = 0, cnt1 = 0;

    boolean go(int v, int col) {
        if (color[v] == -1) {
            color[v] = col;
            if (col == 0) {
                cnt0++;
            } else {
                cnt1++;
            }
            for (int i = 0; i < n; i++) {
                if (g[v][i] && !go(i, 1 - col)) {
                    return false;
                }
            }
            return true;
        } else {
            return color[v] == col;
        }
    }

    void solve() {
        n = in.nextInt();
        g = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], true);
            g[i][i] = false;
        }
        int m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int fr = in.nextInt() - 1;
            int to = in.nextInt() - 1;
            g[fr][to] = g[to][fr] = false;
        }
        color = new int[n];
        Arrays.fill(color, -1);
        List<Integer> sizes = new ArrayList<>();
        List<Integer> sizes2 = new ArrayList<>();
        int can = 0;
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                cnt0 = 0;
                cnt1 = 0;
                if (!go(i, 0)) {
                    out.println(-1);
                    return;
                }
                if (cnt1 == 0) {
                    can += cnt0;
                } else {
                    sizes.add(cnt0);
                    sizes2.add(cnt1);
                }
            }
        }
        boolean[] v = new boolean[n + 1];
        v[0] = true;
        for (int it = 0; it < sizes.size(); it++) {
            int q = sizes.get(it);
            int w = sizes2.get(it);
            boolean[] nv = new boolean[n + 1];
            for (int i = n; i >= 0; i--) {
                if (v[i]) {
                    nv[i + q] = true;
                    nv[i + w] = true;
                }
            }
            v = nv;
        }
        int bestAns = 0;
        for (int firstPart = 0; firstPart <= n; firstPart++) {
            if (!v[firstPart]) {
                continue;
            }
            for (int realFirst = firstPart; realFirst <= firstPart + can; realFirst++) {
                bestAns = Math.max(bestAns, m - f(firstPart) - f(n - firstPart));
            }
        }
        out.println(m - bestAns);
    }

    int f(int x) {
        return x * (x - 1) / 2;
    }

    void solve123() {
        final int MAX = 10000000;
        double[] f = new double[MAX];
        for (int n = 1; n < MAX; n++) {
            f[n] = n / (double) sum(n);
        }
        double curMin = Double.MAX_VALUE;
        for (int i = MAX - 1; i >= 0; i--) {
            if (f[i] <= curMin + 1e-9) {
                if (i < 1000000) {
                    System.err.println(i);
                }
            }
            curMin = Math.min(curMin, f[i]);
        }
    }

    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

Submission Info

Submission Time
Task E - Independence
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 5393 Byte
Status
Exec Time 283 ms
Memory 47100 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt, sample4.txt
All 0 / 700 sample1.txt, sample2.txt, sample3.txt, sample4.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt
Case Name Status Exec Time Memory
1.txt 91 ms 17872 KB
10.txt 102 ms 18644 KB
11.txt 273 ms 42508 KB
12.txt 258 ms 43192 KB
13.txt 263 ms 41188 KB
14.txt 239 ms 44812 KB
15.txt 283 ms 44064 KB
16.txt 248 ms 44660 KB
17.txt 283 ms 45136 KB
18.txt 163 ms 31752 KB
19.txt 281 ms 46388 KB
2.txt 159 ms 33184 KB
20.txt 271 ms 44344 KB
21.txt 271 ms 47100 KB
22.txt 274 ms 42220 KB
23.txt 267 ms 43316 KB
24.txt 241 ms 38748 KB
25.txt 115 ms 20820 KB
26.txt 70 ms 19028 KB
27.txt 70 ms 17748 KB
28.txt 71 ms 21204 KB
29.txt 70 ms 19156 KB
3.txt 279 ms 46660 KB
4.txt 266 ms 45052 KB
5.txt 262 ms 45232 KB
6.txt 269 ms 41096 KB
7.txt 275 ms 42676 KB
8.txt 102 ms 18004 KB
9.txt 166 ms 32912 KB
sample1.txt 73 ms 20820 KB
sample2.txt 70 ms 18260 KB
sample3.txt 72 ms 19796 KB
sample4.txt 72 ms 18772 KB