結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2017-10-29 21:41:44 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 2,495 ms / 4,500 ms |
| コード長 | 7,662 bytes |
| コンパイル時間 | 2,739 ms |
| コンパイル使用メモリ | 85,916 KB |
| 実行使用メモリ | 127,648 KB |
| 最終ジャッジ日時 | 2024-05-01 22:24:38 |
| 合計ジャッジ時間 | 31,863 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 118 ms
58,096 KB |
| testcase_01 | AC | 119 ms
58,052 KB |
| testcase_02 | AC | 117 ms
57,756 KB |
| testcase_03 | AC | 121 ms
57,076 KB |
| testcase_04 | AC | 293 ms
63,516 KB |
| testcase_05 | AC | 303 ms
63,612 KB |
| testcase_06 | AC | 283 ms
63,812 KB |
| testcase_07 | AC | 302 ms
63,716 KB |
| testcase_08 | AC | 2,138 ms
100,444 KB |
| testcase_09 | AC | 2,238 ms
95,620 KB |
| testcase_10 | AC | 2,172 ms
97,984 KB |
| testcase_11 | AC | 2,227 ms
98,568 KB |
| testcase_12 | AC | 1,931 ms
98,948 KB |
| testcase_13 | AC | 1,776 ms
127,648 KB |
| testcase_14 | AC | 1,898 ms
99,468 KB |
| testcase_15 | AC | 2,199 ms
104,032 KB |
| testcase_16 | AC | 2,495 ms
115,520 KB |
| testcase_17 | AC | 2,182 ms
120,692 KB |
| testcase_18 | AC | 2,417 ms
120,988 KB |
| testcase_19 | AC | 2,297 ms
122,432 KB |
ソースコード
import java.util.*;
import java.util.function.*;
class HLDecomposition {
static final boolean DEBUG = false;
int[] p;
ArrayList<Integer>[] child;
int[] weight;
boolean[] isHeavy;
int[] heavyChild;
int[] root;
int[] vertexId;
int[] invVertexId;
void dfs(int v) {
int total = 1;
for (int w: this.child[v]) {
dfs(w);
total += this.weight[w];
}
this.weight[v] = total;
int maxi = -1;
int ma = 0;
for (int w: this.child[v]) {
if (ma < weight[w]) {
maxi = w;
ma = weight[w];
}
}
if (maxi >= 0) {
this.isHeavy[maxi] = true;
this.heavyChild[v] = maxi;
}
}
void dfs2(int v, int root) {
this.root[v] = root;
for (int w: this.child[v]) {
if (isHeavy[w]) {
dfs2(w, root);
} else {
dfs2(w, w);
}
}
}
void bfs() {
int n = this.p.length;
Queue<Integer> queue = new ArrayDeque<Integer>();
queue.add(0);
int count = 0;
while (queue.size() >= 1) {
int current = queue.poll();
for (; current != -1; current = this.heavyChild[current]) {
for (int target: this.child[current]) {
if (this.heavyChild[current] != target) {
queue.add(target);
}
}
this.vertexId[current] = count;
count++;
}
}
if (count != n) {
throw new RuntimeException();
}
for (int i = 0; i < n; ++i) {
this.invVertexId[this.vertexId[i]] = i;
}
}
@SuppressWarnings("unchecked")
HLDecomposition(int[] p) {
this.p = p;
int n = this.p.length;
if (n >= 1 << 18) {
throw new RuntimeException();
}
this.child = new ArrayList[n];
for (int i = 0; i < n; ++i) {
this.child[i] = new ArrayList<Integer>();
}
this.weight = new int[n];
this.isHeavy = new boolean[n];
this.heavyChild = new int[n];
this.root = new int[n];
this.vertexId = new int[n];
this.invVertexId = new int[n];
Arrays.fill(this.isHeavy, false);
Arrays.fill(this.heavyChild, -1);
for (int i = 1; i < n; ++i) {
this.child[p[i]].add(i);
}
dfs(0);
dfs2(0, 0);
bfs();
if (DEBUG) {
System.err.println(Arrays.toString(weight));
System.err.println(Arrays.toString(heavyChild));
System.err.println(Arrays.toString(root));
System.err.println(Arrays.toString(vertexId));
}
}
@FunctionalInterface
static interface QueryFunction {
public abstract void apply(int a, int b, int id, boolean reversed);
}
void decomposeSub(int s, int t, int start, int end, QueryFunction op) {
if (start >= end) {
throw new RuntimeException();
}
if (this.vertexId[s] > this.vertexId[t]) {
op.apply(Math.max(this.vertexId[this.root[s]], this.vertexId[t]),
this.vertexId[s], start, true);
if (this.root[s] != this.root[t]) {
decomposeSub(this.p[this.root[s]], t, start + 1, end, op);
}
} else {
op.apply(Math.max(this.vertexId[this.root[t]], this.vertexId[s]),
this.vertexId[t], end, false);
if (this.root[s] != this.root[t]) {
decomposeSub(s, this.p[this.root[t]], start, end - 1, op);
}
}
}
List<Long> decomposePath(int s, int t) {
List<Long> list = new ArrayList<Long>();
decomposeSub(s, t, 0, 100, (int x, int y, int id, boolean reversed) -> {
list.add((long) id << 37 | (long) x << 19 | (long) y << 1 | (reversed ? 1 : 0));
});
return list;
}
}
class TwoEdgeComponent {
ArrayList<Integer>[] graph;
int[] order, lowlink;
int count;
int[] comp;
boolean[] visited;
int[] tree;
boolean dfs(int v) {
return dfs(v, -1);
}
boolean dfs(int v, int par) {
if (this.order[v] >= 0) {
return false;
}
this.order[v] = count;
count++;
int lowlink = this.order[v];
for (int w: this.graph[v]) {
if (par == w) {
continue;
}
boolean result = dfs(w, v);
if (result) {
lowlink = Math.min(lowlink, this.lowlink[w]);
} else {
lowlink = Math.min(lowlink, this.order[w]);
}
}
this.lowlink[v] = lowlink;
return true;
}
void dfs2(int v, int par, int compId) {
if (this.visited[v]) {
return;
}
this.visited[v] = true;
if (par >= 0 && this.order[par] < this.lowlink[v]) {
// Hasi
compId = this.count;
this.count++;
this.tree[compId] = this.comp[par];
}
this.comp[v] = compId;
for (int w: this.graph[v]) {
dfs2(w, v, compId);
}
}
TwoEdgeComponent(ArrayList<Integer>[] graph) {
int n = graph.length;
this.graph = graph;
this.order = new int[n];
this.lowlink = new int[n];
Arrays.fill(this.order, -1);
Arrays.fill(this.lowlink, -1);
this.count = 0;
dfs(0);
this.count = 1;
this.comp = new int[n];
this.visited = new boolean[n];
this.tree = new int[n];
Arrays.fill(this.tree, -1);
dfs2(0, -1, 0);
}
public static int[] solve(ArrayList<Integer>[] graph, int[] array) {
TwoEdgeComponent comp = new TwoEdgeComponent(graph);
for (int i = 0; i < graph.length; ++i) {
array[i] = comp.comp[i];
}
return Arrays.copyOfRange(comp.tree, 0, comp.count);
}
}
class SegmentTree {
static final int SIZE = 1 << 18;
long[] seg;
SegmentTree() {
this.seg = new long[2 * SIZE];
}
void update(int x, long value) {
x += SIZE - 1;
this.seg[x] = value;
while (x > 0) {
x = (x - 1) / 2;
this.seg[x] = Math.max(this.seg[2 * x + 1], this.seg[2 * x + 2]);
}
}
long query(int l, int r) {
l += SIZE - 1;
r += SIZE - 1;
long y = Long.MIN_VALUE;
while (l < r) {
if ((l & 1) == 0) {
y = Math.max(y, this.seg[l]);
}
if ((r & 1) == 0) {
y = Math.max(y, this.seg[r - 1]);
}
l /= 2;
r = (r - 1) / 2;
}
return y;
}
}
class Main {
@SuppressWarnings("unchecked")
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.next());
int m = Integer.parseInt(scan.next());
int q = Integer.parseInt(scan.next());
ArrayList<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; ++i) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; ++i) {
int a = Integer.parseInt(scan.next()) - 1;
int b = Integer.parseInt(scan.next()) - 1;
graph[a].add(b);
graph[b].add(a);
}
int[] comp = new int[n];
int[] tree = TwoEdgeComponent.solve(graph, comp);
int twon = tree.length;
HLDecomposition hlDecomp = new HLDecomposition(tree);
PriorityQueue<Long>[] queues = new PriorityQueue[twon];
SegmentTree seg = new SegmentTree();
for (int i = 0; i < twon; ++i) {
queues[i] = new PriorityQueue<Long>((Long x, Long y) ->
y.compareTo(x));
queues[i].add(-1L); // banpei
seg.update(i, -1);
}
for (int i = 0; i < q; ++i) {
int kind = Integer.parseInt(scan.next());
if (kind == 1) {
int u = Integer.parseInt(scan.next()) - 1;
int w = Integer.parseInt(scan.next());
int compId = comp[u];
queues[compId].add((long) w << 32 | compId);
seg.update(hlDecomp.vertexId[compId], queues[compId].peek());
} else {
int s = Integer.parseInt(scan.next()) - 1;
int t = Integer.parseInt(scan.next()) - 1;
List<Long> paths = hlDecomp.decomposePath(comp[s], comp[t]);
long maximum = -1;
for (long crypt: paths) {
int id = (int) (crypt >> 37);
int l = (int) (crypt >> 19) & 0x3ffff;
int r = (int) (crypt >> 1) & 0x3ffff;
boolean reversed = crypt % 2 == 1;
maximum = Math.max(maximum, seg.query(l, r + 1));
}
if (maximum == -1) {
// Dare mo inai
System.out.println(-1);
continue;
}
int value = (int) (maximum >>> 32);
int id = (int) maximum;
assert queues[id].peek() == maximum;
System.out.println(value);
queues[id].poll();
assert queues[id].size() >= 1;
seg.update(hlDecomp.vertexId[id], queues[id].peek());
}
}
}
}