結果
| 問題 | No.1326 ふたりのDominator |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2020-12-23 00:40:48 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,603 bytes |
| コンパイル時間 | 895 ms |
| コンパイル使用メモリ | 128,264 KB |
| 実行使用メモリ | 29,944 KB |
| 最終ジャッジ日時 | 2024-06-22 10:31:14 |
| 合計ジャッジ時間 | 6,287 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 RE * 3 |
ソースコード
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[N];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) {}}