結果
| 問題 | No.1326 ふたりのDominator |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2020-12-23 00:43:07 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,611 bytes |
| コンパイル時間 | 1,035 ms |
| コンパイル使用メモリ | 128,324 KB |
| 実行使用メモリ | 18,220 KB |
| 最終ジャッジ日時 | 2024-06-22 10:31:19 |
| 合計ジャッジ時間 | 4,325 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | RE | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
ソースコード
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);
return;
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) {
}
}