結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 nebukuro09
|
| 提出日時 | 2018-04-16 13:10:41 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,030 bytes |
| コンパイル時間 | 1,856 ms |
| コンパイル使用メモリ | 130,912 KB |
| 実行使用メモリ | 88,236 KB |
| 最終ジャッジ日時 | 2023-09-03 19:29:42 |
| 合計ジャッジ時間 | 12,411 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 2 ms
4,384 KB |
| testcase_03 | AC | 1 ms
4,380 KB |
| 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 | AC | 748 ms
88,236 KB |
| testcase_14 | AC | 482 ms
44,944 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
ソースコード
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;
alias Point = Tuple!(int, "x", int, "y", int, "i");
void main() {
auto s = readln.split.map!(to!int);
auto N = s[0];
auto M = s[1];
auto Q = s[2];
auto G = new UndirectedGraph(N);
foreach (_; 0..M) {
s = readln.split.map!(to!int);
G.add_edge(s[0]-1, s[1]-1);
}
G.bridge_decomposition;
int gn = G.group_graph.length.to!int;
auto T = new HLDecomposition(gn);
foreach (i; 0..gn) {
foreach (j; G.group_graph[i]) {
T.add_edge(i, j);
}
}
T.run(0);
auto st = new SegmentTree(gn);
auto W = new BinaryHeap!(Array!int, "a < b")[](gn);
Tuple!(int, int) calc(int u, int v) {
int un = T.nodes[u].serial;
int ug = T.nodes[u].group;
int vn = T.nodes[v].serial;
int vg = T.nodes[v].group;
Tuple!(int, int) ret;
int g = vg;
int last = vn;
while (true) {
if (g == ug && g == vg) {
ret = max(ret, st.query(un, vn));
break;
} else if (g == ug) {
ret = max(ret, st.query(un, last));
break;
} else {
int g_root = T.groups[g].front;
ret = max(ret, st.query(T.nodes[g_root].serial, last));
}
int p = T.group_parent[g];
g = T.nodes[p].group;
last = T.nodes[p].serial;
}
return ret;
}
while (Q--) {
s = readln.split.map!(to!int);
if (s[0] == 1) {
int u = s[1] - 1;
int w = s[2];
u = G.edge_group[u];
int un = T.nodes[u].serial;
int ug = T.nodes[u].group;
W[u].insert(w);
st.assign(un, tuple(W[u].front, u));
} else {
int u = s[1] - 1;
int v = s[2] - 1;
u = G.edge_group[u];
v = G.edge_group[v];
int w = G.lca_group(u, v);
auto t = max(calc(w, u), calc(w, v));
auto maxw = t[0];
auto maxn = t[1];
writeln(maxw == 0 ? -1 : maxw);
if (maxw > 0) {
W[maxn].removeFront;
} else {
continue;
}
if (W[maxn].empty) {
st.assign(T.nodes[maxn].serial, tuple(0, -1));
} else {
st.assign(T.nodes[maxn].serial, tuple(W[maxn].front, maxn));
}
}
}
}
class UndirectedGraph {
int N;
int[][] G;
int[][] dfs_tree;
int[] dfs_subtree;
bool[] dfs_subtree_odd;
int[] ord;
int[] low;
int[] edge_group;
int[][] group_graph;
int[] depth;
int[][] dp;
bool lca_preprocessed = false;
this (int N) {
this.N = N;
G = new int[][](N);
}
void add_edge(int u, int v) {
G[u] ~= v;
G[v] ~= u;
}
int[] articulation_points() {
dfs_tree = new int[][](N);
dfs_subtree = new int[](N);
dfs_subtree_odd = new bool[](N);
ord = new int[](N);
low = new int[](N);
auto used = new bool[](N);
int cnt = 0;
int dfs(int n, int p) {
ord[n] = cnt++;
low[n] = ord[n];
used[n] = true;
foreach (m; G[n]) {
if (m == p) continue;
if (used[m]) low[n] = min(low[n], ord[m]);
else low[n] = min(low[n], dfs(m, n)), dfs_tree[n] ~= m;
}
return low[n];
}
int dfs2(int n, int p) {
dfs_subtree[n] = 1;
foreach (m; dfs_tree[n]) {
if (m == p) continue;
auto s = dfs2(m, n);
if (s % 2) dfs_subtree_odd[n] = true;
dfs_subtree[n] += s;
}
return dfs_subtree[n];
}
int[] ans;
foreach (i; 0..N) if (!used[i]) dfs(i, -1);
foreach (i; 0..N) {
if (ord[i] == 0 && dfs_tree[i].length >= 2) {
ans ~= i;
} else if (ord[i] != 0 && dfs_tree[i].map!(j => (low[j] >= ord[i])).any) {
ans ~= i;
}
}
foreach (i; 0..N) if (ord[i] == 0) dfs2(i, -1);
return ans;
}
void bridge_decomposition() {
auto uf = new UnionFind(N);
edge_group = new int[](N);
edge_group.fill(-1);
int cnt = 0;
articulation_points;
foreach (i; 0..N) {
foreach (j; G[i]) {
if (i > j) continue;
if (ord[i] < low[j]) continue;
uf.unite(i, j);
}
}
foreach (i; 0..N) {
if (uf.table[i] < 0) {
edge_group[i] = cnt++;
}
}
group_graph = new int[][](cnt);
foreach (i; 0..N) {
edge_group[i] = edge_group[uf.find(i)];
}
foreach (i; 0..N) {
foreach (j; G[i]) {
if (i > j) continue;
if (edge_group[i] == edge_group[j]) continue;
group_graph[edge_group[i]] ~= edge_group[j];
group_graph[edge_group[j]] ~= edge_group[i];
}
}
}
void lca_pre() {
void dfs(int n, int p, int d) {
dp[0][n] = p;
depth[n] = d;
foreach (m; group_graph[n]) if (m != p) dfs(m, n, d+1);
}
int K = group_graph.length.to!int;
depth = new int[](K);
dp = new int[][](20, K);
dfs(0, -1, 0);
foreach (k; 0..19)
foreach (n; 0..K)
dp[k+1][n] = (dp[k][n] == -1) ? -1 : dp[k][dp[k][n]];
}
int lca_group(int a, int b) {
if (!lca_preprocessed) {
lca_pre;
lca_preprocessed = true;
}
if (depth[a] < depth[b]) swap(a, b);
auto orig_a = a;
auto orig_b = b;
while (depth[a] > depth[b]) {
int K = 19;
foreach (k; iota(K, -1, -1)) {
if (2^^k <= depth[a] - depth[b]) {
a = dp[k][a];
K = k;
}
}
}
if (a == b) return a;
while (dp[0][a] != dp[0][b]) {
int K = 19;
foreach (k; iota(K, -1, -1)) {
if (dp[k][a] != dp[k][b]) {
a = dp[k][a];
b = dp[k][b];
K = k;
}
}
}
return dp[0][a];
}
}
class UnionFind {
int N;
int[] table;
this(int n) {
N = n;
table = new int[](N);
fill(table, -1);
}
int find(int x) {
return table[x] < 0 ? x : (table[x] = find(table[x]));
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (table[x] > table[y]) swap(x, y);
table[x] += table[y];
table[y] = x;
}
}
class HLDecomposition {
alias Node = Tuple!(int, "group", int, "number", int, "serial");
int N;
int[][] G;
int[][] groups;
int[] parent;
int[] group_parent;
Node[] nodes;
int[] serial_number;
this (int N) {
this.N = N;
G = new int[][](N);
nodes = new Node[](N);
parent = new int[](N);
}
void add_edge(int u, int v) {
G[u] ~= v;
}
void run(int root) {
auto subtree_size = dfs_subtree_size(root);
int group_count = -1;
void decompose(int n, int p, bool heavy) {
if (!heavy) {
group_count += 1;
groups.length += 1;
group_parent ~= p;
}
parent[n] = p;
nodes[n] = Node(group_count, groups[group_count].length.to!int, 0);
groups[group_count] ~= n;
bool first = true;
G[n].sort!((a, b) => subtree_size[a] > subtree_size[b]);
foreach (m; G[n]) {
if (m == p) continue;
decompose(m, n, first);
first = false;
}
}
decompose(root, -1, false);
group_count += 1;
int cnt = 0;
foreach (g; groups) foreach (n; g) nodes[n].serial = cnt++;
}
int[] dfs_subtree_size(int root) {
auto subtree_size = new int[](N);
int dfs(int n, int p) {
subtree_size[n] = 1;
foreach (m; G[n]) if (m != p) subtree_size[n] += dfs(m, n);
return subtree_size[n];
}
dfs(root, -1);
return subtree_size;
}
}
class SegmentTree {
Tuple!(int, int)[] table;
int size;
this(int n) {
assert(bsr(n) < 29);
size = 1 << (bsr(n) + 2);
table = new Tuple!(int, int)[](size);
}
void assign(int pos, Tuple!(int, int) num) {
return assign(pos, num, 0, 0, size/2-1);
}
void assign(int pos, Tuple!(int, int) num, int i, int left, int right) {
if (left == right) {
table[i] = num;
return;
}
auto mid = (left + right) / 2;
if (pos <= mid)
assign(pos, num, i*2+1, left, mid);
else
assign(pos, num, i*2+2, mid+1, right);
table[i] = max(table[i*2+1], table[i*2+2]);
}
Tuple!(int, int) query(int pl, int pr) {
return query(pl, pr, 0, 0, size/2-1);
}
Tuple!(int, int) query(int pl, int pr, int i, int left, int right) {
if (pl > right || pr < left)
return tuple(0, -1);
else if (pl <= left && right <= pr)
return table[i];
else
return
max(query(pl, pr, i*2+1, left, (left+right)/2),
query(pl, pr, i*2+2, (left+right)/2+1, right));
}
}