Submission #2730473


Source Code Expand

Copy
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

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<>();
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                cnt0 = 0;
                cnt1 = 0;
                if (!go(i, 0)) {
                    out.println(-1);
                    return;
                }
                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;
            }
            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("Main23.in"));
            out = new PrintWriter(new File("Main23.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 700
Code Size 5238 Byte
Status
Exec Time 311 ms
Memory 48676 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt, sample4.txt
All 700 / 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 129 ms 21716 KB
10.txt 98 ms 19028 KB
11.txt 255 ms 47632 KB
12.txt 269 ms 45384 KB
13.txt 257 ms 42624 KB
14.txt 235 ms 45472 KB
15.txt 270 ms 44552 KB
16.txt 244 ms 46544 KB
17.txt 259 ms 43112 KB
18.txt 159 ms 30192 KB
19.txt 276 ms 45652 KB
2.txt 156 ms 29952 KB
20.txt 273 ms 42952 KB
21.txt 263 ms 44520 KB
22.txt 267 ms 41948 KB
23.txt 271 ms 44956 KB
24.txt 237 ms 37324 KB
25.txt 74 ms 19028 KB
26.txt 68 ms 21204 KB
27.txt 68 ms 21204 KB
28.txt 69 ms 17620 KB
29.txt 69 ms 18644 KB
3.txt 257 ms 48340 KB
4.txt 311 ms 43492 KB
5.txt 253 ms 48676 KB
6.txt 266 ms 44584 KB
7.txt 277 ms 44144 KB
8.txt 104 ms 21332 KB
9.txt 158 ms 30576 KB
sample1.txt 69 ms 22228 KB
sample2.txt 70 ms 17364 KB
sample3.txt 70 ms 18644 KB
sample4.txt 69 ms 20436 KB