#212971 (Java) No.529 帰省ラッシュ

• 問題: No.529 帰省ラッシュ
• ユーザー: 夕叢霧香(ゆうむらきりか)
• 提出日時: 2017-10-29 21:34:33
• 言語: Java (openjdk 23)
• 結果: RE
• 実行時間: -
• コード長: 7,644 bytes
• コンパイル時間: 3,166 ms
• コンパイル使用メモリ: 96,784 KB
• 実行使用メモリ: 116,952 KB
• 最終ジャッジ日時: 2024-11-22 05:36:03
• 合計ジャッジ時間: 30,138 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 7 RE * 11

ソースコード

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(id, queues[id].peek());
	    }
	}
    }
}