AtCoder Regular Contest 039

Submission #4065801

Source codeソースコード

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];

    auto G = new UndirectedGraph(N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G.add_edge(s[0]-1, s[1]-1);
    }

    auto T = new BridgeBlockTree(G);
    auto L = new LCA(T.block.length.to!int, 0);

    foreach (i; 0..T.block.length.to!int) {
        foreach (j; T.adj[i]) {
            if (i < j) {
                L.add_edge(i, j);
            }
        }
    }

    bool check() {
        s = readln.split.map!(to!int);
        auto a = T.index[s[0] - 1];
        auto b = T.index[s[1] - 1];
        auto c = T.index[s[2] - 1];
        auto ab = L.lca(a, b);
        auto bc = L.lca(b, c);
        auto ca = L.lca(c, a);

        if (ca == a) {
            return ab == a && bc == b;
        } else if (ca == c) {
            return bc == c && ab == b;
        } else {
            return ab == ca || bc == ca;
        }
    }


    auto Q = readln.chomp.to!int;

    while (Q--) {
        writeln( check ? "OK" : "NG" );
    }
}



class UndirectedGraph {
    int N;
    int[][] adj;

    this (int N) {
        this.N = N;
        adj = new int[][](N);
    }

    void add_edge(int u, int v) {
        adj[u] ~= v;
        adj[v] ~= u;
    }
}

class BridgeBlockTree : UndirectedGraph { // 二重辺連結成分分解 (橋で分解したあとの木)
    int[] index;
    int[][] block;
    Tuple!(int, int)[] bridges;

    this (UndirectedGraph g) {
        int n = 0;
        int cnt = 0;

        bridges = detect_bridges(g);
        auto is_bridge = new bool[int][](g.N);
        foreach (b; bridges) {
            is_bridge[b[0]][b[1]] = true;
            is_bridge[b[1]][b[0]] = true;
        }

        index = new int[](g.N);
        auto used = new bool[](g.N);

        void dfs(int n) {
            index[n] = block.length.to!int - 1;
            block.back ~= n;
            used[n] = true;
            foreach (m; g.adj[n]) {
                if (used[m] || m in is_bridge[n]) continue;
                dfs(m);
            }
        }

        foreach (u; 0..g.N) {
            if (used[u]) continue;
            block.length += 1;
            dfs(u);
        }

        super(block.length.to!int);

        foreach (u; 0..g.N) {
            foreach (v; g.adj[u]) {
                if (u < v && index[u] != index[v]) {
                    adj[index[u]] ~= index[v];
                    adj[index[v]] ~= index[u];
                }
            }
        }
    }

    Tuple!(int, int)[] detect_bridges(UndirectedGraph g) {
        Tuple!(int, int)[] bridges;
        int cnt = 0;
        auto ord = new int[](g.N);
        auto low = new int[](g.N);
        fill(ord, -1);
        fill(low, -1);

        void dfs(int n, int p) {
            ord[n] = low[n] = cnt++;
            foreach (m; g.adj[n]) {
                if (m == p) continue;
                if (ord[m] == -1) dfs(m, n);
                low[n] = min(low[n], low[m]);
                if (ord[n] < low[m]) bridges ~= tuple(n, m);
            }
        }

        dfs(0, -1);
        return bridges;
    }
}


class LCA {
    int n, root, lgn;
    int[][] g;
    int[] depth;
    int[][] dp;
    bool constructed = false;

    this(int n, int root) {
        this.n = n;
        this.root = root;
        lgn = bsr(n) + 1;
        g = new int[][](n);
        depth = new int[](n);
        dp = new int[][](n, lgn);
    }

    void add_edge(int u, int v) {
        g[u] ~= v;
        g[v] ~= u;
    }

    void construct() {
        auto stack = new Tuple!(int, int, int)[](n+10);
        int sp = 0;
        stack[0] = tuple(root, -1, 0);
        while (sp >= 0) {
            auto u = stack[sp][0];
            auto p = stack[sp][1];
            auto d = stack[sp][2];
            sp -= 1;
            dp[u][0] = p;
            depth[u] = d;
            foreach (v; g[u]) if (v != p) stack[++sp] = tuple(v, u, d+1);
        }

        foreach (k; 0..lgn-1)
            foreach (i; 0..n)
                dp[i][k+1] = (dp[i][k] == -1) ? -1 : dp[dp[i][k]][k];
        constructed = true;
    }

    void dfs(int u, int p, int d) {
        dp[u][0] = p;
        depth[u] = d;
        foreach (v; g[u]) if (v != p) dfs(v, u, d+1);
    }

    int lca(int a, int b) {
        if (!constructed) construct;
        if (depth[a] < depth[b]) swap(a, b);

        int diff = depth[a] - depth[b];
        foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[a][i];

        if (a == b) return a;

        int K = lgn;
        while (dp[a][0] != dp[b][0]) {
            foreach_reverse (k; 0..lgn) {
                if (dp[a][k] != dp[b][k]) {
                    a = dp[a][k];
                    b = dp[b][k];
                    K = k;
                }
            }
        }

        return dp[a][0];
    }
}

Submission

Task問題 D - 旅行会社高橋君
User nameユーザ名 nebukuro09
Created time投稿日時
Language言語 D (LDC 0.17.0)
Status状態 WA
Score得点 0
Source lengthソースコード長 5207 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_0.txt,sample_1.txt,sample_2.txt
All 0 / 100 bigcycleandsub_0.txt,bigcycleandsub_1.txt,cluster_0.txt,cluster_1.txt,cluster_2.txt,cluster_3.txt,cluster_4.txt,cycleline_0.txt,cycleline_1.txt,cycleline_2.txt,cycleline_3.txt,cycleline_4.txt,cycletree_0.txt,cycletree_1.txt,cycletree_2.txt,cycletree_3.txt,cycletree_4.txt,large_0.txt,large_1.txt,large_2.txt,line_0.txt,line_1.txt,lineandsub_0.txt,lineandsub_1.txt,lineandsub_2.txt,maxrand_0.txt,maxrand_1.txt,maxrand_2.txt,maxrandandsub_0.txt,maxrandandsub_1.txt,maxrandandsub_2.txt,maxrandandsub_3.txt,maxrandandsub_4.txt,med_0.txt,med_1.txt,med_2.txt,med_3.txt,med_4.txt,med_5.txt,med_6.txt,med_7.txt,med_8.txt,med_9.txt,perfect_0.txt,perfect_1.txt,perfect_2.txt,sample_0.txt,sample_1.txt,sample_2.txt,small_0.txt,small_1.txt,small_2.txt,small_3.txt,small_4.txt,small_5.txt,small_6.txt,small_7.txt,small_8.txt,small_9.txt,star_0.txt,star_1.txt,star_2.txt,tencluster_0.txt,tencluster_1.txt,tencluster_2.txt,tencluster_3.txt,tencluster_4.txt,tree_0.txt,tree_1.txt,tree_2.txt,verysmall_0.txt,verysmall_1.txt,verysmall_2.txt,verysmall_3.txt,verysmall_4.txt,verysmall_5.txt,verysmall_6.txt,verysmall_7.txt,verysmall_8.txt,verysmall_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
bigcycleandsub_0.txt WA
bigcycleandsub_1.txt WA
cluster_0.txt WA
cluster_1.txt WA
cluster_2.txt WA
cluster_3.txt WA
cluster_4.txt AC 265 ms 24060 KB
cycleline_0.txt WA
cycleline_1.txt WA
cycleline_2.txt WA
cycleline_3.txt WA
cycleline_4.txt WA
cycletree_0.txt WA
cycletree_1.txt WA
cycletree_2.txt WA
cycletree_3.txt WA
cycletree_4.txt WA
large_0.txt AC 252 ms 30204 KB
large_1.txt AC 47 ms 7804 KB
large_2.txt AC 167 ms 19708 KB
line_0.txt WA
line_1.txt WA
lineandsub_0.txt WA
lineandsub_1.txt WA
lineandsub_2.txt WA
maxrand_0.txt AC 266 ms 32892 KB
maxrand_1.txt AC 270 ms 32892 KB
maxrand_2.txt AC 271 ms 32892 KB
maxrandandsub_0.txt WA
maxrandandsub_1.txt WA
maxrandandsub_2.txt WA
maxrandandsub_3.txt WA
maxrandandsub_4.txt WA
med_0.txt AC 4 ms 636 KB
med_1.txt AC 2 ms 380 KB
med_2.txt AC 3 ms 508 KB
med_3.txt AC 3 ms 636 KB
med_4.txt AC 4 ms 764 KB
med_5.txt AC 3 ms 636 KB
med_6.txt AC 3 ms 764 KB
med_7.txt AC 3 ms 636 KB
med_8.txt AC 2 ms 380 KB
med_9.txt AC 3 ms 636 KB
perfect_0.txt AC 91 ms 8828 KB
perfect_1.txt AC 71 ms 7548 KB
perfect_2.txt AC 94 ms 8828 KB
sample_0.txt AC 1 ms 256 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
small_0.txt WA
small_1.txt AC 2 ms 380 KB
small_2.txt AC 1 ms 256 KB
small_3.txt WA
small_4.txt AC 2 ms 380 KB
small_5.txt AC 2 ms 380 KB
small_6.txt AC 1 ms 256 KB
small_7.txt WA
small_8.txt WA
small_9.txt AC 1 ms 380 KB
star_0.txt WA
star_1.txt WA
star_2.txt WA
tencluster_0.txt WA
tencluster_1.txt WA
tencluster_2.txt WA
tencluster_3.txt WA
tencluster_4.txt WA
tree_0.txt WA
tree_1.txt WA
tree_2.txt WA
verysmall_0.txt AC 1 ms 256 KB
verysmall_1.txt WA
verysmall_2.txt WA
verysmall_3.txt AC 1 ms 256 KB
verysmall_4.txt AC 1 ms 256 KB
verysmall_5.txt AC 1 ms 256 KB
verysmall_6.txt WA
verysmall_7.txt AC 1 ms 256 KB
verysmall_8.txt WA
verysmall_9.txt AC 1 ms 256 KB