Submission #1868122

---

Source Code Expand

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static final int[] dr8 = new int[] { 0, -1, -1, -1, 0, 1, 1, 1, };
    private static final int[] dc8 = new int[] { -1, -1, 0, 1, 1, 1, 0, -1, };

    static final Watch watch = new Watch();
    static final XorShift rng = new XorShift(System.nanoTime());

    private static final int EMPTY = (1 << 10) - 1;

    private int NV;
    private int S0;
    private int S;

    private IntArray[] connectedVs;
    private IntArray[] connectedVsEmb;

    private boolean[][] isConnected;
    private int[][] isConnectedEmb;
    private int[][] inverseEmb;

    private int score;
    private int bestScore = (int) -1e9;
    private int scoreBase = 5000;
    private int scoreAdd = 0;
    private int scoreBonus = 0;
    private int scoreLoss = 0;

    private int sumScores() {
        return scoreBase + scoreAdd + scoreBonus - scoreLoss;
    }

    private IntArray[] embVSets;
    private int preservedEdges;
    private int NE;

    private String[] run(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
        init(NV, NE, u, v, NEmbV, NEmbE, a, b);
        solve();
        String[] solution = makeSolution();
        return solution;
    }

    private void init(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
        this.NV = NV;
        this.NE = NE;

        for (int i = 0; i < u.length; i++) {
            u[i]--;
        }
        for (int i = 0; i < v.length; i++) {
            v[i]--;
        }

        preservedEdges = 0;
        this.isConnected = new boolean[NV][NV];
        for (int i = 0; i < u.length; i++) {
            isConnected[u[i]][v[i]] = true;
            isConnected[v[i]][u[i]] = true;
        }

        connectedVs = new IntArray[NV];
        for (int i = 0; i < connectedVs.length; i++) {
            connectedVs[i] = new IntArray(1 << 9);
        }
        for (int i = 0; i < u.length; i++) {
            connectedVs[u[i]].add(v[i]);
            connectedVs[v[i]].add(u[i]);
        }
        this.isConnectedEmb = new int[NV][NV];
        for (int i = 0; i < NV; i++) {
            Arrays.fill(isConnectedEmb[i], -1);
        }
        connectedVsEmb = new IntArray[NV];
        for (int i = 0; i < connectedVsEmb.length; i++) {
            connectedVsEmb[i] = new IntArray(1 << 9);
        }
        for (int i = 0; i < a.length; i++) {
            a[i]--;
        }
        for (int i = 0; i < b.length; i++) {
            b[i]--;
        }

        S0 = (int) Math.sqrt(NEmbV + 1e-9);
        S = S0;
        if (S >= NV) {
            S = NV;
        }
        embVSets = new IntArray[NV];
        for (int i = 0; i < embVSets.length; i++) {
            embVSets[i] = new IntArray(1 << 9);
        }
        bestEmbVSets = new IntArray[NV];
        for (int i = 0; i < bestEmbVSets.length; i++) {
            bestEmbVSets[i] = new IntArray(1 << 9);
        }

        inverseEmb = new int[S][S];
        for (int r = 0; r < S; r++) {
            for (int c = 0; c < S; c++) {
                inverseEmb[r][c] = EMPTY;
            }
        }

        scoreLoss -= NV;
    }

    private void solve() {

        greedy();

        score = scoreAdd;
        saveBest();
        SA();
    }

    private void greedy() {

        int v = 0;
        int usedPoints = 0;
        for (int r = 0; r < S; r++) {

            if (v >= NV) {
                break;
            }

            int length = (S * S - usedPoints) / (NV - v);

            for (int c = 0; c < S; c++) {
                if (inverseEmb[r][c] != EMPTY) {
                    continue;
                }

                int r2 = r;
                int c2 = c;
                for (int l = 0; l < length; l++) {
                    if (inverseEmb[r2][c2] != EMPTY) {
                        break;
                    }

                    if (v >= NV) {
                        int r3;
                        int c3;
                        if (isLowerRightDirection(r2, c2)) {
                            r3 = r2 - dr8[5];
                            c3 = c2 - dc8[5];
                        } else {
                            r3 = r2 - dr8[7];
                            c3 = c2 - dc8[7];
                        }
                        if (!isValid(r3, 0, S)) {
                            break;
                        }
                        if (!isValid(c3, 0, S)) {
                            if (c3 < 0) {
                                c3 = 0;
                            } else if (c3 >= S) {
                                c3 = S - 1;
                            }
                        }
                        add(toEmbV(r2, c2), inverseEmb[r3][c3]);
                    } else {
                        add(toEmbV(r2, c2), v);
                    }
                    usedPoints++;

                    if (isLowerRightDirection(r2, c2)) {
                        r2 += dr8[5];
                        c2 += dc8[5];
                    } else {
                        r2 += dr8[7];
                        c2 += dc8[7];
                    }

                    if (!isValid(r2, 0, S)) {
                        break;
                    } else if (!isValid(c2, 0, S)) {
                        if (c2 < 0) {
                            c2 = 0;
                        } else if (c2 >= S) {
                            c2 = S - 1;
                        }
                    }
                }

                v++;
            }
        }

    }

    private boolean isLowerRightDirection(int r2, int c2) {
        return (r2 + c2) % 2 == 0;
    }

    private boolean add(int embV, int v) {
        int embR = toEmbR(embV);
        int embC = toEmbC(embV);
        assert inverseEmb[embR][embC] == EMPTY;
        assert checkCanAdd(v, embR, embC);

        inverseEmb[embR][embC] = v;
        embVSets[v].add(embV);
        scoreLoss++;
        for (int d = 0; d < dr8.length; d++) {
            int embNextR = embR + dr8[d];
            int embNextC = embC + dc8[d];
            if (!isValid(embNextR, 0, S)) {
                continue;
            }
            if (!isValid(embNextC, 0, S)) {
                continue;
            }
            if (inverseEmb[embNextR][embNextC] == EMPTY) {
                continue;
            }
            int nextV = inverseEmb[embNextR][embNextC];
            assert nextV >= 0 && nextV < NV;
            if (!isConnected[nextV][v]) {
                continue;
            }
            if (isConnectedEmb[nextV][v] >= 0) {
                continue;
            }

            isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
            connectedVsEmb[v].add(nextV);

            isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
            connectedVsEmb[nextV].add(v);
            scoreAdd += 100;
            preservedEdges++;
            if (preservedEdges == NE) {
                scoreBonus += 100000;
            }

        }
        return true;
    }

    private boolean adds(int[] embVs, int start, int end, int v) {
        for (int i = start; i < end; i++) {
            int embV = embVs[i];
            int embR = toEmbR(embV);
            int embC = toEmbC(embV);
            assert inverseEmb[embR][embC] == EMPTY;
            inverseEmb[embR][embC] = v;
            embVSets[v].add(embV);
            scoreLoss++;
            for (int d = 0; d < dr8.length; d++) {
                int embNextR = embR + dr8[d];
                int embNextC = embC + dc8[d];
                if (!isValid(embNextR, 0, S)) {
                    continue;
                }
                if (!isValid(embNextC, 0, S)) {
                    continue;
                }
                if (inverseEmb[embNextR][embNextC] == EMPTY) {
                    continue;
                }
                int nextV = inverseEmb[embNextR][embNextC];
                assert nextV >= 0 && nextV < NV;
                if (!isConnected[v][nextV]) {
                    continue;
                }
                if (isConnectedEmb[v][nextV] >= 0) {
                    continue;
                }
                isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
                connectedVsEmb[v].add(nextV);
                isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
                connectedVsEmb[nextV].add(v);
                scoreAdd += 100;
                preservedEdges++;
                if (preservedEdges == NE) {
                    scoreBonus += 100000;
                }
            }
        }
        return true;
    }

    private IntArray change = new IntArray();

    private int simulateAdds(int[] embVs, int start, int end, int v) {
        countUsed++;

        update(embVs, start, end, v);

        int score = 0;

        for (int i = start; i < end; i++) {
            int embV = embVs[i];
            int embR = toEmbR(embV);
            int embC = toEmbC(embV);
            for (int d = 0; d < dr8.length; d++) {
                int embNextR = embR + dr8[d];
                int embNextC = embC + dc8[d];
                if (!isValid(embNextR, 0, S)) {
                    continue;
                }
                if (!isValid(embNextC, 0, S)) {
                    continue;
                }
                if (inverseEmb[embNextR][embNextC] == EMPTY) {
                    continue;
                }
                int nextV = inverseEmb[embNextR][embNextC];
                assert nextV >= 0 && nextV < NV;
                if (!isConnected[nextV][v]) {
                    continue;
                }

                if (used[nextV] == countUsed) {
                    continue;
                }
                used[nextV] = countUsed;
                score += 100;
            }
        }
        return score;

    }

    private void update(int[] embVs, int start, int end, int v) {
        for (int i = start; i < end; i++) {
            int embV = embVs[i];
            int embR = toEmbR(embV);
            int embC = toEmbC(embV);
            change.add((embR << 20) | (embC << 10) | (inverseEmb[embR][embC]));
            inverseEmb[embR][embC] = v;
        }
    }

    private boolean checkCanAdd(int v, int embR, int embC) {
        boolean b = embVSets[v].length == 0;
        boolean b2 = false;
        if (!b) {
            for (int d = 0; d < dr8.length; d++) {
                int embNextR = embR + dr8[d];
                int embNextC = embC + dc8[d];
                if (!isValid(embNextR, 0, S)) {
                    continue;
                }
                if (!isValid(embNextC, 0, S)) {
                    continue;
                }
                if (inverseEmb[embNextR][embNextC] == EMPTY) {
                    continue;
                }
                int nextV = inverseEmb[embNextR][embNextC];
                if (nextV == v) {
                    b2 = true;
                    break;
                }
            }
        }
        boolean b3 = b || b2;
        return b3;
    }

    private boolean removeAll(int v) {

        for (int i = 0; i < embVSets[v].length; i++) {
            int embV = embVSets[v].values[i];

            int embR = toEmbR(embV);
            int embC = toEmbC(embV);
            inverseEmb[embR][embC] = EMPTY;

        }
        scoreLoss -= embVSets[v].length;
        embVSets[v].clear();

        for (int i = connectedVsEmb[v].length - 1; i >= 0; i--) {
            int nextV = connectedVsEmb[v].values[i];
            remove(v, nextV);
            remove(nextV, v);
            scoreAdd -= 100;
            preservedEdges--;
            if (preservedEdges + 1 == NE) {
                scoreBonus -= 100000;
            }
        }
        return true;

    }

    private void remove(int v, int nextV) {
        int index = isConnectedEmb[v][nextV];
        IntArray vs = connectedVsEmb[v];
        if (index != vs.length - 1) {
            int otherV = vs.values[vs.length - 1];
            vs.values[vs.length - 1] = vs.values[index];
            vs.values[index] = otherV;
            isConnectedEmb[v][otherV] = index;
        }
        vs.remove();
        isConnectedEmb[v][nextV] = -1;
    }

    private int[] used = new int[1 << 9];
    private int countUsed = 0;
    private SAState sa = new SAState();

    private void SA() {
        int mask = (1 << 10) - 1;

        sa.init();
        for (;; sa.loop++) {
            if ((sa.loop & mask) == 0) {
                sa.updateTime();

                if (sa.isTLE()) {
                    loadBest();
                    break;
                }

                sa.updateTemperature();
            }

            change();
        }
    }

    private void change() {
        int random = (int) (3 * rng.nextDouble());
        if (random == 0) {
            swap();
        } else if (random == 1) {
            changeLength();
        } else {
            moveLine();
        }
    }

    private IntArray embVs1 = new IntArray();
    private IntArray embVs2 = new IntArray();
    private IntArray embVs3 = new IntArray();

    private void moveLine() {
        int v = (int) (NV * rng.nextDouble());

        boolean isUpper = rng.nextDouble() < 0.5;

        int embV0;
        {
            assert checkOrder(v);
            IntArray embVSet = embVSets[v];
            embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            int embR0 = toEmbR(embV0);
            if (embR0 == 0) {
                isUpper = false;
                embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            } else if (embR0 == S - 1) {
                isUpper = true;
                embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            }
        }

        int sameLineV = EMPTY;
        int embR0 = toEmbR(embV0);
        int embC0 = toEmbC(embV0);
        if (isLowerRightDirection(embR0, embC0)) {
            if (isUpper) {
                int r1 = embR0 + dr8[1];
                int c1 = embC0 + dc8[1];
                if (c1 < 0) {
                    c1 = 0;
                } else if (c1 >= S) {
                    c1 = S - 1;
                }
                if (isValid(r1, 0, S)) {
                    assert inverseEmb[r1][c1] != v;
                    assert inverseEmb[r1][c1] != EMPTY;
                    sameLineV = inverseEmb[r1][c1];
                }
            } else {
                int r5 = embR0 + dr8[5];
                int c5 = embC0 + dc8[5];
                if (c5 < 0) {
                    c5 = 0;
                } else if (c5 >= S) {
                    c5 = S - 1;
                }
                if (isValid(r5, 0, S)) {
                    assert inverseEmb[r5][c5] != v;
                    assert inverseEmb[r5][c5] != EMPTY;
                    sameLineV = inverseEmb[r5][c5];
                }
            }
        } else {
            if (isUpper) {
                int r3 = embR0 + dr8[3];
                int c3 = embC0 + dc8[3];
                if (c3 < 0) {
                    c3 = 0;
                } else if (c3 >= S) {
                    c3 = S - 1;
                }
                if (isValid(r3, 0, S)) {
                    assert inverseEmb[r3][c3] != v;
                    assert inverseEmb[r3][c3] != EMPTY;
                    sameLineV = inverseEmb[r3][c3];
                }
            } else {
                int r7 = embR0 + dr8[7];
                int c7 = embC0 + dc8[7];
                if (c7 < 0) {
                    c7 = 0;
                } else if (c7 >= S) {
                    c7 = S - 1;
                }
                if (isValid(r7, 0, S)) {
                    assert inverseEmb[r7][c7] != v;
                    assert inverseEmb[r7][c7] != EMPTY;
                    sameLineV = inverseEmb[r7][c7];
                }
            }
        }

        if (sameLineV == EMPTY) {
            return;
        }

        int toV = (int) (NV * rng.nextDouble());
        for (int k = 0; k < NV; k++) {
            if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
                toV = (int) (NV * rng.nextDouble());
            } else {
                break;
            }
        }
        if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
            return;
        }

        int currentLengthToV = embVSets[toV].length;
        boolean vIsUpperAtToV = rng.nextDouble() < 0.5;

        if (isUpper) {
            embVs1.clear();
            for (int i = 0; i < embVSets[sameLineV].length; i++) {
                embVs1.add(embVSets[sameLineV].values[i]);
            }
            for (int i = 0; i < embVSets[v].length; i++) {
                embVs1.add(embVSets[v].values[i]);
            }
        } else {
            embVs1.clear();
            for (int i = 0; i < embVSets[v].length; i++) {
                embVs1.add(embVSets[v].values[i]);
            }
            for (int i = 0; i < embVSets[sameLineV].length; i++) {
                embVs1.add(embVSets[sameLineV].values[i]);
            }
        }
        embVs3.clear();
        for (int i = 0; i < embVSets[toV].length; i++) {
            embVs3.add(embVSets[toV].values[i]);
        }

        int newLengthV = 1 + (int) ((currentLengthToV - 1) * rng.nextDouble());
        int newLengthToV = currentLengthToV - newLengthV;
        assert newLengthV > 0;
        assert newLengthToV > 0;

        int beforeV = -100 * connectedVsEmb[v].length;
        int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
        if (isConnectedEmb[sameLineV][v] >= 0) {
            beforeSameLineV += 100;
        }
        int beforeToV = -100 * connectedVsEmb[toV].length;
        if (isConnectedEmb[toV][v] >= 0) {
            beforeToV += 100;
        }
        if (isConnectedEmb[toV][sameLineV] >= 0) {
            beforeToV += 100;
        }

        if (vIsUpperAtToV) {
            update(embVs3.values, 0, newLengthV, EMPTY);
            update(embVs3.values, newLengthV, newLengthV + newLengthToV, EMPTY);
        } else {
            update(embVs3.values, 0, newLengthToV, EMPTY);
            update(embVs3.values, newLengthToV, newLengthToV + newLengthV, EMPTY);
        }

        int afterSameLineV = simulateAdds(embVs1.values, 0, embVs1.length, sameLineV);
        int afterV;
        int afterToV;
        if (vIsUpperAtToV) {
            afterV = simulateAdds(embVs3.values, 0, newLengthV, v);
            afterToV = simulateAdds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
        } else {
            afterToV = simulateAdds(embVs3.values, 0, newLengthToV, toV);
            afterV = simulateAdds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
        }

        int newScore = score + beforeV + beforeToV + beforeSameLineV + afterV + afterToV + afterSameLineV;

        for (int i = change.length - 1; i >= 0; i--) {
            int value = change.values[i];
            int embR = (value >>> 20) & ((1 << 10) - 1);
            int embC = (value >>> 10) & ((1 << 10) - 1);
            int v3 = (value >>> 0) & ((1 << 10) - 1);
            inverseEmb[embR][embC] = v3;
        }
        change.clear();
        if (newScore >= score || sa.accept(newScore, score)) {
            removeAll(v);
            removeAll(sameLineV);
            removeAll(toV);

            adds(embVs1.values, 0, embVs1.length, sameLineV);
            if (vIsUpperAtToV) {
                adds(embVs3.values, 0, newLengthV, v);
                adds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
            } else {
                adds(embVs3.values, 0, newLengthToV, toV);
                adds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
            }

            score = newScore;

            saveBest();
        }

    }

    private void changeLength() {
        int v = (int) (NV * rng.nextDouble());

        boolean isUpper = rng.nextDouble() < 0.5;

        int embV0;
        {
            assert checkOrder(v);
            IntArray embVSet = embVSets[v];
            embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            int embR0 = toEmbR(embV0);
            if (embR0 == 0) {
                isUpper = false;
                embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            } else if (embR0 == S - 1) {
                isUpper = true;
                embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
            }
        }

        int sameLineV = EMPTY;
        int embR0 = toEmbR(embV0);
        int embC0 = toEmbC(embV0);
        if (isLowerRightDirection(embR0, embC0)) {
            if (isUpper) {
                int r1 = embR0 + dr8[1];
                int c1 = embC0 + dc8[1];
                if (c1 < 0) {
                    c1 = 0;
                } else if (c1 >= S) {
                    c1 = S - 1;
                }
                if (isValid(r1, 0, S)) {
                    assert inverseEmb[r1][c1] != v;
                    assert inverseEmb[r1][c1] != EMPTY;
                    sameLineV = inverseEmb[r1][c1];
                }
            } else {
                int r5 = embR0 + dr8[5];
                int c5 = embC0 + dc8[5];
                if (c5 < 0) {
                    c5 = 0;
                } else if (c5 >= S) {
                    c5 = S - 1;
                }
                if (isValid(r5, 0, S)) {
                    assert inverseEmb[r5][c5] != v;
                    assert inverseEmb[r5][c5] != EMPTY;
                    sameLineV = inverseEmb[r5][c5];
                }
            }
        } else {
            if (isUpper) {
                int r3 = embR0 + dr8[3];
                int c3 = embC0 + dc8[3];
                if (c3 < 0) {
                    c3 = 0;
                } else if (c3 >= S) {
                    c3 = S - 1;
                }
                if (isValid(r3, 0, S)) {
                    assert inverseEmb[r3][c3] != v;
                    assert inverseEmb[r3][c3] != EMPTY;
                    sameLineV = inverseEmb[r3][c3];
                }
            } else {
                int r7 = embR0 + dr8[7];
                int c7 = embC0 + dc8[7];
                if (c7 < 0) {
                    c7 = 0;
                } else if (c7 >= S) {
                    c7 = S - 1;
                }
                if (isValid(r7, 0, S)) {
                    assert inverseEmb[r7][c7] != v;
                    assert inverseEmb[r7][c7] != EMPTY;
                    sameLineV = inverseEmb[r7][c7];
                }
            }
        }

        if (sameLineV == EMPTY) {
            return;
        }

        embVs1.clear();
        if (isUpper) {
            for (int i = 0; i < embVSets[sameLineV].length; i++) {
                embVs1.add(embVSets[sameLineV].values[i]);
            }
            for (int i = 0; i < embVSets[v].length; i++) {
                embVs1.add(embVSets[v].values[i]);
            }
        } else {
            for (int i = 0; i < embVSets[v].length; i++) {
                embVs1.add(embVSets[v].values[i]);
            }
            for (int i = 0; i < embVSets[sameLineV].length; i++) {
                embVs1.add(embVSets[sameLineV].values[i]);
            }
        }

        int currentLengthV = embVSets[v].length;
        int currentLengthV2 = embVSets[sameLineV].length;

        int beforeV = -100 * connectedVsEmb[v].length;
        int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
        if (isConnectedEmb[sameLineV][v] >= 0) {
            beforeSameLineV += 100;
        }

        int newLengthV = 1 + (int) ((currentLengthV + currentLengthV2 - 1) * rng.nextDouble());
        int newLengthV2 = currentLengthV + currentLengthV2 - newLengthV;
        assert newLengthV > 0;
        assert newLengthV2 > 0;

        int afterV;
        int afterSameLineV;
        if (isUpper) {
            update(embVs1.values, newLengthV2, newLengthV + newLengthV2, EMPTY);
            afterSameLineV = simulateAdds(embVs1.values, 0, newLengthV2, sameLineV);
            afterV = simulateAdds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
        } else {
            update(embVs1.values, newLengthV, newLengthV + newLengthV2, EMPTY);
            afterV = simulateAdds(embVs1.values, 0, newLengthV, v);
            afterSameLineV = simulateAdds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
        }

        int newScore = score + beforeV + beforeSameLineV + afterV + afterSameLineV;

        for (int i = change.length - 1; i >= 0; i--) {
            int value = change.values[i];
            int embR = (value >>> 20) & ((1 << 10) - 1);
            int embC = (value >>> 10) & ((1 << 10) - 1);
            int v3 = (value >>> 0) & ((1 << 10) - 1);
            inverseEmb[embR][embC] = v3;
        }
        change.clear();
        if (newScore >= score || sa.accept(newScore, score)) {
            removeAll(v);
            removeAll(sameLineV);

            if (isUpper) {
                adds(embVs1.values, 0, newLengthV2, sameLineV);
                adds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
            } else {
                adds(embVs1.values, 0, newLengthV, v);
                adds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
            }

            score = newScore;
            saveBest();
        }
    }

    private boolean checkOrder(int v) {
        IntArray embVSet = embVSets[v];
        for (int i = 1; i < embVSet.length; i++) {
            if (toEmbR(embVSet.values[i - 1]) >= toEmbR(embVSet.values[i])) {
                return false;
            }
        }
        return true;
    }

    private void swap() {
        int v0 = (int) (NV * rng.nextDouble());
        int embV0 = embVSets[v0].values[(int) (embVSets[v0].length * rng.nextDouble())];
        int embR0 = toEmbR(embV0);
        int embC0 = toEmbC(embV0);

        int embNextR = -1;
        int embNextC = -1;
        while (!isValid(embNextR, 0, S) || !isValid(embNextC, 0, S) || inverseEmb[embNextR][embNextC] == v0) {
            int d = (int) (dr8.length * rng.nextDouble());
            embNextR = embR0 + dr8[d];
            embNextC = embC0 + dc8[d];
        }

        int v = inverseEmb[embNextR][embNextC];

        int v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
        for (int k = 0; k < 3; k++) {
            if (v2 != v) {
                break;
            }
            v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
        }
        if (v2 == v) {
            return;
        }

        embVs1.clear();
        for (int i = 0; i < embVSets[v].length; i++) {
            embVs1.add(embVSets[v].values[i]);
        }
        embVs2.clear();
        for (int i = 0; i < embVSets[v2].length; i++) {
            embVs2.add(embVSets[v2].values[i]);
        }

        int beforeV = -100 * connectedVsEmb[v].length;
        int beforeV2 = -100 * connectedVsEmb[v2].length;
        if (isConnectedEmb[v2][v] >= 0) {
            beforeV2 += 100;
        }

        update(embVs2.values, 0, embVs2.length, EMPTY);
        int afterV2 = simulateAdds(embVs1.values, 0, embVs1.length, v2);
        int afterV = simulateAdds(embVs2.values, 0, embVs2.length, v);

        int newScore = score + beforeV + beforeV2 + afterV + afterV2;

        for (int i = change.length - 1; i >= 0; i--) {
            int value = change.values[i];
            int embR = (value >>> 20) & ((1 << 10) - 1);
            int embC = (value >>> 10) & ((1 << 10) - 1);
            int v3 = (value >>> 0) & ((1 << 10) - 1);
            inverseEmb[embR][embC] = v3;
        }
        change.clear();
        if (newScore >= score || sa.accept(newScore, score)) {
            removeAll(v);
            removeAll(v2);

            adds(embVs1.values, 0, embVs1.length, v2);
            adds(embVs2.values, 0, embVs2.length, v);

            score = newScore;
            saveBest();

        }
    }

    private IntArray[] bestEmbVSets;

    private void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            for (int v = 0; v < NV; v++) {
                System.arraycopy(embVSets[v].values, 0, bestEmbVSets[v].values, 0, embVSets[v].length);
                bestEmbVSets[v].length = embVSets[v].length;
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int v = 0; v < NV; v++) {
            System.arraycopy(bestEmbVSets[v].values, 0, embVSets[v].values, 0, bestEmbVSets[v].length);
            embVSets[v].length = bestEmbVSets[v].length;
        }
    }

    private String[] makeSolution() {
        String[] res = new String[NV];
        for (int v = 0; v < NV; v++) {

            IntArray embVSet = embVSets[v];

            StringBuilder resV = new StringBuilder();
            resV.append(embVSet.length);
            for (int i = 0; i < embVSet.length; i++) {
                int embV = embVSet.values[i];
                resV.append(" " + (embV + 1));
            }
            res[v] = resV.toString();
        }
        return res;
    }

    private boolean isValid(int v, int min, int sup) {
        return v >= min && v < sup;
    }

    private int toEmbV(int embR, int embC) {
        return embR * S0 + embC;
    }

    private int toEmbC(int embV) {
        return embV % S0;
    }

    private int toEmbR(int embV) {
        return embV / S0;
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            String line = br.readLine();
            String[] split = line.split(" ");
            int NV = Integer.parseInt(split[0]);
            int NE = Integer.parseInt(split[1]);

            int[] u = new int[NE];
            int[] v = new int[NE];
            for (int i = 0; i < NE; i++) {
                line = br.readLine();
                split = line.split(" ");
                u[i] = Integer.parseInt(split[0]);
                v[i] = Integer.parseInt(split[1]);
            }

            line = br.readLine();
            split = line.split(" ");
            int NEmbV = Integer.parseInt(split[0]);
            int NEmbE = Integer.parseInt(split[1]);

            int[] a = new int[NEmbE];
            int[] b = new int[NEmbE];
            for (int i = 0; i < NEmbE; i++) {
                line = br.readLine();
                split = line.split(" ");
                a[i] = Integer.parseInt(split[0]);
                b[i] = Integer.parseInt(split[1]);
            }

            Main main = new Main();
            String[] ret = main.run(NV, NE, u, v, NEmbV, NEmbE, a, b);
            for (int i = 0; i < ret.length; ++i) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

class Edge {
    int u;
    int v;

    public Edge(int u, int v) {
        super();
        this.u = u;
        this.v = v;
    }

}

class IntArray {
    public int[] values;
    public int length;

    public IntArray() {
        this(new int[4], 0);
    }

    public IntArray(int capacity) {
        this(new int[capacity], 0);
    }

    public IntArray(int[] values) {
        this(values, values.length);
    }

    public IntArray(int[] values, int length) {
        this.values = values;
        this.length = length;
    }

    public void add(int value) {
        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        values[length++] = value;
    }

    public int remove() {
        return values[--length];
    }

    public boolean contains(int value) {
        for (int i = 0; i < length; i++) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        length = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < length; i++) {
            sb.append(values[i] + ",");
        }
        sb.append("}");
        return sb.toString();
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public int remove(int index) {
        if (index >= length) {
            throw new AssertionError();
        }

        if (index == length - 1) {
            return remove();
        }

        int res = values[index];
        System.arraycopy(values, index + 1, values, index, length - (index + 1));
        length--;

        return res;
    }

    public void set(int index, int value) {
        if (index == length) {
            add(value);
            return;
        }

        if (index >= length) {
            throw new AssertionError();
        }

        if (length >= values.length - 1) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        System.arraycopy(values, index, values, index + 1, length - index);
        length++;

        values[index] = value;
    }

    public IntArray copy() {
        return new IntArray(Arrays.copyOf(values, length), length);
    }

    public int[] toArray() {
        return Arrays.copyOf(values, length);
    }

}

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 29.5;
    public double time = startTime;

    public double startTemperature = 50;
    public double endTemperature = 5;
    public double temperature = startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 1 << 20;
    public double endRange = 1 << 20;
    public double range = startRange;

    public int loop;
    public int countChange;
    public int countAccept;

    public void init() {
        loop = 0;
        countChange = 0;
        countAccept = 0;
        lastAcceptTemperature = startTemperature;
        startTime = useTime ? Main.watch.getSecond() : loop;

        updateTime();
        updateTemperature();
        updateRange();
    }

    public void updateTemperature() {
        temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateTime() {
        time = useTime ? Main.watch.getSecond() : loop;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double newScore, double currentScore) {
        assert newScore - currentScore < 0;
        assert temperature >= 0;
        return Main.rng.nextDouble() < Math.exp((newScore - currentScore) / (temperature));
    }

}

Submission Info

Judge Result