Submission #1060013


Source Code Expand

/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.4.0"
+/

import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons, std.math;

// import dcomp.scanner, dcomp.graph.namori;

alias E = Tuple!(int, "to");

long calc(E[][] g, int[] co) {
    int n = g.length.to!int;
    if (co.sum) return 10L^^18;
    long[] sm = new long[n];
    void dfs(int p, int b) {
        sm[p] = co[p];
        foreach (e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p);
            sm[p] += sm[d];
        }
    }
    dfs(0, -1);
    return sm.map!"abs(a)".sum;
}

long solve(E[][] g) {
    int n = g.length.to!int;
    int[] col = new int[n];
    void dfs(int p, int b, int c) {
        col[p] = c;
        foreach (e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p, -c);
        }
    }
    dfs(0, -1, 1);
    return calc(g, col);
}


int main() {
    auto sc = new Scanner(stdin);
    int n, m;
    sc.read(n, m);
    E[][] g = new E[][n];
    foreach (i; 0..m) {
        int a, b;
        sc.read(a, b); a--; b--;
        g[a] ~= E(b);
        g[b] ~= E(a);
    }
    if (n % 2) {
        writeln(-1);
        return 0;
    }
    if (m == n-1) {
        //not namori
        auto ans = solve(g);
        if (ans == 10L^^18) ans = -1;
        writeln(ans);
        return 0;
    }
    auto nmr = namori(g);
    auto cy = nmr.cycles[0];
    
    int a = cy[0], b = cy[1];
    g[a] = g[a].remove!(e => e.to == b);
    g[b] = g[b].remove!(e => e.to == a);

    
    int[] col = new int[n];
    void dfs(int p, int b, int c) {
        col[p] = c;
        foreach (E e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p, -c);
        }
    }
    dfs(a, -1, 1);
    if (col.sum < 0) {
        col[] *= -1;
    }

    if (cy.length % 2 == 0) {
        if (col.sum) {
            writeln(-1);
            return 0;
        }
        long check(int md) {
            auto buf = col.dup;
            buf[a] += md;
            buf[b] -= md;
//            writeln(md, " ", buf, calc(g, buf));
            return calc(g, buf)+abs(md);
        }
        int l = -2*n, r = 2*n;
//        assert(check(l-1) >= check(l));
//        assert(check(r) <= check(r+1));
        while (r-l > 5) {
            int mdl = (l+l+r)/3;
            int mdr = (l+r+r)/3;
            if (check(mdl) > check(mdr)) {
                l = mdl;
            } else {
                r = mdr;
            }
        }
        writeln(iota(l, r+1).map!(md => check(md)).reduce!"min(a, b)");
//        assert(false);
    } else {
        int ad = col.sum/2;
        col[a] -= ad;
        col[b] -= ad;
        writeln(ad + calc(g, col));
    }

    return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/namori.d */
// module dcomp.graph.namori;

// import dcomp.graph.dfsinfo;

struct Namori {
    bool[] isCycle;
    int[][] cycles;
    int[] root;
    this(int n) {
        isCycle = new bool[n];
        root = new int[n];
    }
}

Namori namori(T)(T g) {
    import std.algorithm : find, each;
    import std.range;
    import std.conv : to;
    int n = g.length.to!int;
    auto info = dfsInfo(g);
    auto nmr = Namori(n);
    with (nmr) {
        //find self loop
        foreach (i; 0..n) {
            if (g[i].find!(e => e.to == i).empty) continue;
            isCycle[i] = true;
            cycles ~= [i];
        }
        foreach (p; info.vlis) {
            if (info.low[p] == info.ord[p]) continue;
            if (g[p].length == info.tr[p].length+1) continue;
            int[] v;
            int nw = p;
            while (info.ord[nw] != info.low[p]) {
                v ~= nw;
                nw = info.par[nw];
            }
            v ~= nw;
            v.each!(i => isCycle[i] = true);
            cycles ~= v;
        }
        bool[] used = new bool[n];
        void dfs(int p, int b, int r) {
            if (used[p]) return;
            used[p] = true;
            root[p] = r;
            foreach (e; g[p]) {
                int d = e.to;
                if (d == b) continue;
                if (isCycle[d]) continue;
                dfs(d, p, r);
            }
        }
        foreach (i; 0..n) {
            if (!isCycle[i]) continue;
            dfs(i, -1, i);
        }
    }
    return nmr;
}

Namori directedNamori(int[] g) {
    import std.algorithm : find, each;
    import std.range;
    import std.conv : to;
    int n = g.length.to!int;
    auto nmr = Namori(n);
    with (nmr) {
        int[] used = new int[n]; used[] = -1;
        foreach (i; 0..n) {
            if (used[i] != -1) continue;
            int j = i;
            while (used[j] == -1) {
                used[j] = i;
                j = g[j];
            }
            if (used[j] != i) continue;
            int k = j;
            int[] cy = [];
            while (true) {
                cy ~= k;
                isCycle[k] = true;
                if (g[k] == j) break;
                k = g[k];
            }
            cycles ~= cy;
        }
        int[] dp = new int[n]; dp[] = -1;
        int dfs(int p) {
            if (isCycle[p]) return p;
            if (dp[p] != -1) return dp[p];
            return dp[p] = dfs(g[p]);
        }
        foreach (i; 0..n) {
            root[i] = dfs(i);
        }
    }
    return nmr;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    string[] buf;
    private bool succ() {
        while (!buf.length) {
            if (f.eof) return false;
            buf = f.readln.split;
        }
        return true;
    }
    private bool readSingle(T)(ref T x) {
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                //string or char[10] etc
                x = buf.front;
                buf.popFront;
            } else {
                static if (isStaticArray!T) {
                    //static
                    assert(buf.length == T.length);
                }
                x = buf.map!(to!E).array;
                buf.length = 0;                
            }
        } else {
            x = buf.front.to!T;
            buf.popFront;            
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}

unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    fout.writeln("1 2 3");
    fout.writeln("ab cde");
    fout.writeln("1.0 1.0 2.0");
    fout.close;
    Scanner sc = new Scanner(File(fileName, "r"));
    int a;
    int[2] b;
    char[2] c;
    string d;
    double e;
    double[] f;
    sc.read(a, b, c, d, e, f);
    assert(a == 1);
    assert(equal(b[], [2, 3]));
    assert(equal(c[], "ab"));
    assert(equal(d, "cde"));
    assert(e == 1.0);
    assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/dfsinfo.d */
// module dcomp.graph.dfsinfo;

struct DFSInfo {
    int[] low, ord, par, vlis; //low, ord, parent, visitList
    int[][] tr; //dfs tree(directed)
    this(int n) {
        low = new int[n];
        ord = new int[n];
        par = new int[n];
        vlis = new int[n];
        tr = new int[][](n);
    }
}

DFSInfo dfsInfo(T)(T g) {
    import std.algorithm : min, each, filter;
    import std.conv : to;
    const int n = g.length.to!int;
    auto info = DFSInfo(n);
    with(info) {
        int co = 0;
        bool[] used = new bool[](n);
        void dfs(int p, int b) {
            used[p] = true;
            low[p] = ord[p] = co++;
            par[p] = b;

            bool rt = true;
            foreach (e; g[p]) {
                int d = e.to;
                if (rt && d == b) {
                    rt = false;
                    continue;
                }
                if (!used[d]) {
                    dfs(d, p);
                    low[p] = min(low[p], low[d]);
                } else {
                    low[p] = min(low[p], ord[d]);
                }
            }
        }
            
        foreach (i; 0..n) {
            if (used[i]) continue;
            dfs(i, -1);
        }
        par.filter!"a!=-1".each!((i, v) => tr[v] ~= i.to!int);
        ord.each!((i, v) => vlis[v] = i.to!int);
    }
    return info;
}

Submission Info

Submission Time
Task F - Namori
User yosupo
Language D (LDC 0.17.0)
Score 2200
Code Size 9289 Byte
Status AC
Exec Time 505 ms
Memory 30460 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 1500 / 1500 700 / 700
Status
AC × 4
AC × 20
AC × 66
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
Subtask1 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt
Case Name Status Exec Time Memory
0_00.txt AC 2 ms 256 KB
0_01.txt AC 2 ms 256 KB
0_02.txt AC 2 ms 256 KB
0_03.txt AC 2 ms 256 KB
1_00.txt AC 2 ms 256 KB
1_01.txt AC 117 ms 17404 KB
1_02.txt AC 108 ms 13564 KB
1_03.txt AC 98 ms 12028 KB
1_04.txt AC 112 ms 14204 KB
1_05.txt AC 114 ms 13948 KB
1_06.txt AC 114 ms 13948 KB
1_07.txt AC 111 ms 13180 KB
1_08.txt AC 116 ms 14460 KB
1_09.txt AC 106 ms 11772 KB
1_10.txt AC 107 ms 11516 KB
1_11.txt AC 110 ms 11516 KB
1_12.txt AC 112 ms 11388 KB
1_13.txt AC 101 ms 10236 KB
1_14.txt AC 106 ms 10748 KB
1_15.txt AC 112 ms 11388 KB
1_16.txt AC 101 ms 10236 KB
1_17.txt AC 109 ms 11388 KB
2_00.txt AC 2 ms 256 KB
2_01.txt AC 503 ms 30460 KB
2_02.txt AC 383 ms 26492 KB
2_03.txt AC 237 ms 22652 KB
2_04.txt AC 462 ms 26492 KB
2_05.txt AC 482 ms 26364 KB
2_06.txt AC 497 ms 26364 KB
2_07.txt AC 475 ms 26364 KB
2_08.txt AC 499 ms 26364 KB
2_09.txt AC 335 ms 22268 KB
2_10.txt AC 389 ms 22524 KB
2_11.txt AC 435 ms 22524 KB
2_12.txt AC 467 ms 22652 KB
2_13.txt AC 108 ms 10236 KB
2_14.txt AC 136 ms 14844 KB
2_15.txt AC 471 ms 22780 KB
2_16.txt AC 101 ms 10236 KB
2_17.txt AC 462 ms 22780 KB
2_18.txt AC 2 ms 256 KB
2_19.txt AC 131 ms 19708 KB
2_20.txt AC 111 ms 15996 KB
2_21.txt AC 505 ms 30460 KB
2_22.txt AC 146 ms 19324 KB
2_23.txt AC 143 ms 19452 KB
2_24.txt AC 150 ms 19324 KB
2_25.txt AC 144 ms 19452 KB
2_26.txt AC 146 ms 19324 KB
2_27.txt AC 138 ms 15356 KB
2_28.txt AC 139 ms 15228 KB
2_29.txt AC 135 ms 15612 KB
2_30.txt AC 140 ms 15228 KB
2_31.txt AC 101 ms 10236 KB
2_32.txt AC 144 ms 15484 KB
2_33.txt AC 140 ms 15228 KB
2_34.txt AC 99 ms 10236 KB
2_35.txt AC 141 ms 15228 KB
2_36.txt AC 234 ms 22268 KB
2_37.txt AC 234 ms 22268 KB
2_38.txt AC 234 ms 22652 KB
2_39.txt AC 236 ms 22268 KB
2_40.txt AC 236 ms 22652 KB
2_41.txt AC 234 ms 22268 KB
2_42.txt AC 238 ms 22268 KB
2_43.txt AC 234 ms 22268 KB