Submission #4065801


Source Code Expand

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 Info

Submission Time
Task D - 旅行会社高橋君
User nebukuro09
Language D (LDC 0.17.0)
Score 0
Code Size 5207 Byte
Status WA
Exec Time 450 ms
Memory 77948 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 35
WA × 45
Set Name Test Cases
Sample sample_0.txt, sample_1.txt, sample_2.txt
All 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
Case Name Status Exec Time Memory
bigcycleandsub_0.txt WA 197 ms 34300 KB
bigcycleandsub_1.txt WA 208 ms 34940 KB
cluster_0.txt WA 270 ms 24188 KB
cluster_1.txt WA 268 ms 24188 KB
cluster_2.txt WA 265 ms 24060 KB
cluster_3.txt WA 267 ms 24188 KB
cluster_4.txt AC 265 ms 24060 KB
cycleline_0.txt WA 219 ms 13564 KB
cycleline_1.txt WA 227 ms 13564 KB
cycleline_2.txt WA 236 ms 13436 KB
cycleline_3.txt WA 232 ms 13436 KB
cycleline_4.txt WA 218 ms 13564 KB
cycletree_0.txt WA 221 ms 22268 KB
cycletree_1.txt WA 219 ms 13052 KB
cycletree_2.txt WA 219 ms 13052 KB
cycletree_3.txt WA 218 ms 13052 KB
cycletree_4.txt WA 220 ms 13052 KB
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 359 ms 73084 KB
line_1.txt WA 292 ms 64380 KB
lineandsub_0.txt WA 450 ms 75388 KB
lineandsub_1.txt WA 421 ms 77948 KB
lineandsub_2.txt WA 425 ms 76412 KB
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 300 ms 36988 KB
maxrandandsub_1.txt WA 298 ms 35452 KB
maxrandandsub_2.txt WA 297 ms 36348 KB
maxrandandsub_3.txt WA 311 ms 35452 KB
maxrandandsub_4.txt WA 296 ms 36220 KB
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 2 ms 380 KB
small_1.txt AC 2 ms 380 KB
small_2.txt AC 1 ms 256 KB
small_3.txt WA 1 ms 256 KB
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 2 ms 380 KB
small_8.txt WA 2 ms 380 KB
small_9.txt AC 1 ms 380 KB
star_0.txt WA 338 ms 73724 KB
star_1.txt WA 326 ms 74620 KB
star_2.txt WA 347 ms 73980 KB
tencluster_0.txt WA 261 ms 25340 KB
tencluster_1.txt WA 261 ms 24828 KB
tencluster_2.txt WA 268 ms 24700 KB
tencluster_3.txt WA 264 ms 25468 KB
tencluster_4.txt WA 265 ms 25468 KB
tree_0.txt WA 440 ms 71420 KB
tree_1.txt WA 422 ms 71420 KB
tree_2.txt WA 430 ms 72060 KB
verysmall_0.txt AC 1 ms 256 KB
verysmall_1.txt WA 1 ms 256 KB
verysmall_2.txt WA 1 ms 256 KB
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 1 ms 256 KB
verysmall_7.txt AC 1 ms 256 KB
verysmall_8.txt WA 1 ms 256 KB
verysmall_9.txt AC 1 ms 256 KB