結果

問題 No.529 帰省ラッシュ
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-10-29 21:53:32
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,582 ms / 4,500 ms
コード長 7,714 bytes
コンパイル時間 2,356 ms
コンパイル使用メモリ 97,648 KB
実行使用メモリ 117,128 KB
最終ジャッジ日時 2024-05-09 17:04:47
合計ジャッジ時間 32,740 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
45,660 KB
testcase_01 AC 119 ms
45,520 KB
testcase_02 AC 121 ms
45,640 KB
testcase_03 AC 121 ms
45,548 KB
testcase_04 AC 297 ms
52,480 KB
testcase_05 AC 303 ms
52,348 KB
testcase_06 AC 289 ms
52,384 KB
testcase_07 AC 293 ms
52,476 KB
testcase_08 AC 2,276 ms
97,580 KB
testcase_09 AC 2,228 ms
93,832 KB
testcase_10 AC 2,267 ms
88,964 KB
testcase_11 AC 2,422 ms
89,708 KB
testcase_12 AC 1,957 ms
88,792 KB
testcase_13 AC 1,608 ms
117,128 KB
testcase_14 AC 2,391 ms
91,144 KB
testcase_15 AC 2,462 ms
95,080 KB
testcase_16 AC 2,582 ms
106,332 KB
testcase_17 AC 2,224 ms
112,196 KB
testcase_18 AC 2,249 ms
113,052 KB
testcase_19 AC 2,240 ms
113,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.util.*;
import java.util.function.*;
class HLDecomposition {
    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 = Arrays.copyOf(p, p.length);
	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();
    }
    @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 implements Runnable {
    // https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%81%AE%E6%8B%A1%E5%BC%B5
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start(); //16MBスタックを確保して実行
    }
    @SuppressWarnings("unchecked")
    public void run() {
	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 treeN = tree.length;
	HLDecomposition hlDecomp = new HLDecomposition(tree);
	PriorityQueue<Long>[] queues = new PriorityQueue[treeN];
	SegmentTree seg = new SegmentTree();
	for (int i = 0; i < treeN; ++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());
	    }
	}
    }
}
0