結果

問題 No.1326 ふたりのDominator
ユーザー 👑 hos.lyrichos.lyric
提出日時 2020-12-23 00:43:34
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 5,603 bytes
コンパイル時間 868 ms
コンパイル使用メモリ 114,628 KB
実行使用メモリ 33,712 KB
最終ジャッジ日時 2023-09-04 11:44:41
合計ジャッジ時間 6,336 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 5 ms
4,380 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 5 ms
4,384 KB
testcase_10 AC 5 ms
4,380 KB
testcase_11 AC 5 ms
4,376 KB
testcase_12 AC 298 ms
21,300 KB
testcase_13 AC 285 ms
20,476 KB
testcase_14 AC 290 ms
21,304 KB
testcase_15 AC 290 ms
22,300 KB
testcase_16 AC 287 ms
20,200 KB
testcase_17 AC 251 ms
19,988 KB
testcase_18 AC 268 ms
18,480 KB
testcase_19 AC 197 ms
18,616 KB
testcase_20 AC 309 ms
29,892 KB
testcase_21 AC 336 ms
29,700 KB
testcase_22 AC 405 ms
33,712 KB
testcase_23 AC 223 ms
18,600 KB
testcase_24 AC 299 ms
22,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


int N, M;
int[] A, B;
int[][] G;

int zeit;
int[] par, pari, outdeg, dis, low;
int stackLen;
int[] stack;
int[][] ess;
void dfs(int u, int p, int pi) {
  par[u] = p;
  pari[u] = pi;
  outdeg[u] = 0;
  dis[u] = low[u] = zeit++;
  foreach (i; G[u]) {
    if (i != pi) {
      const v = A[i] ^ B[i] ^ u;
      if (dis[u] > dis[v]) {
        stack[stackLen++] = i;
      }
      if (dis[v] == -1) {
        ++outdeg[u];
        dfs(v, u, i);
        chmin(low[u], low[v]);
        if (dis[u] <= low[v]) {
          int[] es;
          for (; ; ) {
            const e = stack[--stackLen];
            es ~= e;
            if (e == i) {
              break;
            }
          }
          ess ~= es;
        }
      } else {
        chmin(low[u], dis[v]);
      }
    }
  }
}

enum E = 18;

int V, artsLen, essLen;
int[][] GRAPH;
int[][] PAR;
int[] DEP, DP;

int LCA(int u, int v) {
  foreach_reverse (e; 0 .. E) {
    if (DEP[u] - (1 << e) >= DEP[v]) {
      u = PAR[e][u];
    }
    if (DEP[v] - (1 << e) >= DEP[u]) {
      v = PAR[e][v];
    }
  }
  foreach_reverse (e; 0 .. E) {
    if (PAR[e][u] != PAR[e][v]) {
      u = PAR[e][u];
      v = PAR[e][v];
    }
  }
  if (u != v) {
    u = PAR[0][u];
    v = PAR[0][v];
  }
  return u;
}

void DFS(int u, int p) {
  PAR[0][u] = p;
  DEP[u] = (p == -1) ? 0 : (DEP[p] + 1);
  DP[u] = (p == -1) ? 0 : DP[p];
  if (u < artsLen) {
    ++DP[u];
  }
  foreach (v; GRAPH[u]) {
    if (v != p) {
      DFS(v, u);
    }
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      M = readInt();
      A = new int[M];
      B = new int[M];
      foreach (i; 0 .. M) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      const Q = readInt();
      auto X = new int[Q];
      auto Y = new int[Q];
      foreach (q; 0 .. Q) {
        X[q] = readInt() - 1;
        Y[q] = readInt() - 1;
      }
      
      G = new int[][N];
      foreach (i; 0 .. M) {
        G[A[i]] ~= i;
        G[B[i]] ~= i;
      }
      zeit = 0;
      par = new int[N];
      pari = new int[N];
      outdeg = new int[N];
      dis = new int[N];
      dis[] = -1;
      low = new int[N];
      stackLen = 0;
      stack = new int[M];
      ess = [];
      dfs(0, -1, -1);
      essLen = cast(int)(ess.length);
      debug {
        writeln("ess = ", ess);
      }
      
      auto isArt = new bool[N];
      int[] arts;
      foreach (u; 0 .. N) {
        if (pari[u] == -1) {
          isArt[u] = (outdeg[u] >= 2);
        } else {
          foreach (i; G[u]) {
            if (i != pari[u]) {
              const v = A[i] ^ B[i] ^ u;
              if (dis[u] <= low[v]) {
                isArt[u] = true;
              }
            }
          }
        }
        if (isArt[u]) {
          arts ~= u;
        }
      }
      artsLen = cast(int)(arts.length);
      debug {
        writeln("arts = ", arts);
      }
      
      auto idXs = new int[N];
      idXs[] = -1;
      foreach (x; 0 .. artsLen) {
        idXs[arts[x]] = x;
      }
      auto idYs = new int[M];
      idYs[] = -1;
      foreach (y; 0 .. essLen) {
        foreach (i; ess[y]) {
          idYs[i] = artsLen + y;
        }
      }
      
      V = artsLen + essLen;
      GRAPH = new int[][V];
      foreach (x; 0 .. artsLen) {
        int[] ys;
        foreach (i; G[arts[x]]) {
          ys ~= idYs[i];
        }
        ys = ys.sort.uniq.array;
        foreach (y; ys) {
          GRAPH[x] ~= y;
          GRAPH[y] ~= x;
        }
      }
      debug {
        writeln("GRAPH = ", GRAPH);
      }
      PAR = new int[][](E, V);
      DEP = new int[V];
      DP = new int[V];
      DFS(0, -1);
      foreach (e; 0 .. E - 1) {
        foreach (x; 0 .. V) {
          PAR[e + 1][x] = (PAR[e][x] == -1) ? -1 : PAR[e][PAR[e][x]];
        }
      }
      debug {
        writeln("DEP = ", DEP);
        writeln("DP = ", DP);
      }
      
      int get(int u) {
        return (isArt[u]) ? idXs[u] : idYs[G[u][0]];
      }
      foreach (q; 0 .. Q) {
        int ans;
        if (X[q] != Y[q]) {
          const x = get(X[q]);
          const y = get(Y[q]);
          const l = LCA(x, y);
          debug {
            writeln(X[q], " ", Y[q], ": ", x, " ", y, " ", l);
          }
          ans = DP[x] + DP[y] - 2 * DP[l];
          if (x < artsLen) --ans;
          if (y < artsLen) --ans;
          if (l < artsLen) ++ans;
        }
        writeln(ans);
      }
    }
  } catch (EOFException e) {
  }
}
0