結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 37zigen
|
| 提出日時 | 2017-06-11 05:39:43 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 2,643 ms / 4,500 ms |
| コード長 | 11,678 bytes |
| コンパイル時間 | 2,652 ms |
| コンパイル使用メモリ | 91,680 KB |
| 実行使用メモリ | 155,532 KB |
| 最終ジャッジ日時 | 2024-09-24 15:59:08 |
| 合計ジャッジ時間 | 24,217 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 51 ms
50,456 KB |
| testcase_01 | AC | 53 ms
50,512 KB |
| testcase_02 | AC | 52 ms
50,404 KB |
| testcase_03 | AC | 52 ms
50,468 KB |
| testcase_04 | AC | 118 ms
52,356 KB |
| testcase_05 | AC | 120 ms
52,368 KB |
| testcase_06 | AC | 121 ms
52,128 KB |
| testcase_07 | AC | 122 ms
52,188 KB |
| testcase_08 | AC | 1,017 ms
86,720 KB |
| testcase_09 | AC | 1,525 ms
92,888 KB |
| testcase_10 | AC | 2,643 ms
121,068 KB |
| testcase_11 | AC | 2,566 ms
115,788 KB |
| testcase_12 | AC | 935 ms
87,628 KB |
| testcase_13 | AC | 1,087 ms
145,160 KB |
| testcase_14 | AC | 826 ms
89,440 KB |
| testcase_15 | AC | 1,744 ms
125,132 KB |
| testcase_16 | AC | 1,782 ms
136,876 KB |
| testcase_17 | AC | 1,568 ms
154,236 KB |
| testcase_18 | AC | 1,586 ms
150,840 KB |
| testcase_19 | AC | 1,660 ms
155,532 KB |
ソースコード
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
class State {
int i;
int parent;
int j;// 操作後g[i][j]に潜る
public State(int i_, int parent_, int j_) {
i = i_;
parent = parent_;
j = j_;
}
}
int two_edge_connected_componets(ArrayList<Integer>[] g, int[] col) {
int n = g.length;
Arrays.fill(col, -1);
int cols = 0;
int[] low = new int[n];
int[] ord = new int[n];
boolean[] marked = new boolean[n];
Arrays.fill(low, -1);
Arrays.fill(ord, -1);
int order = 0;
ArrayDeque<State> stk = new ArrayDeque<>();
ArrayDeque<Integer> pnd = new ArrayDeque<>();
for (int ii = 0; ii < n; ++ii) {
if (ord[ii] == -1) {
stk.add(new State(ii, -1, 0));
}
while (!stk.isEmpty()) {
State s = stk.pollFirst();
if (ord[s.i] == -1) {
low[s.i] = (ord[s.i] = order++);
pnd.addFirst(s.i);
}
if (s.j > 0 && s.parent != g[s.i].get(s.j - 1) && !marked[g[s.i].get(s.j - 1)]) {
low[s.i] = Math.min(low[s.i], low[g[s.i].get(s.j - 1)]);
}
if (s.j == g[s.i].size() && low[s.i] == ord[s.i]) {
while (true) {
int v = pnd.pollFirst();
col[v] = cols;
marked[v] = true;
if (v == s.i)
break;
}
++cols;
}
if (s.j == g[s.i].size())
continue;
int v = g[s.i].get(s.j);
stk.addFirst(new State(s.i, s.parent, s.j + 1));
if (ord[v] == -1) {
stk.addFirst(new State(v, s.i, 0));
} else if (v != s.parent && !marked[v]) {
low[s.i] = Math.min(low[s.i], low[v]);
}
}
}
return cols;
}
@SuppressWarnings("unchecked")
public void solve() {
int n = ni();
int m = ni();
int q = ni();
ArrayList<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<>();
}
for (int i = 0; i < m; ++i) {
int a = ni() - 1;
int b = ni() - 1;
g[a].add(b);
g[b].add(a);
}
int[] col = new int[n];
int cols = two_edge_connected_componets(g, col);
ArrayList<Integer>[] h = new ArrayList[cols];
PriorityQueue<Long>[] w = new PriorityQueue[cols];
for (int i = 0; i < cols; ++i) {
w[i] = new PriorityQueue<>(new Comparator<Long>() {
@Override
public int compare(Long o1, Long o2) {
return -Long.compare(o1, o2);
}
});
}
for (int i = 0; i < cols; ++i) {
w[i].add(-1L);
}
for (int i = 0; i < cols; ++i) {
h[i] = new ArrayList<>();
}
for (int i = 0; i < n; ++i) {
for (int j : g[i]) {
int a = col[i];
int b = col[j];
if (a == b)
continue;
if (h[a].contains(b))
continue;
h[a].add(b);
h[b].add(a);
}
}
for (int i = 0; i < cols; ++i) {
Collections.sort(h[i]);
for (int j = 0; j < h[i].size(); ++j) {
while (j + 1 < h[i].size() && h[i].get(j) == h[i].get(j + 1)) {
h[i].remove(j + 1);
}
}
}
HLDecomposition hl = new HLDecomposition(cols);
for (int i = 0; i < cols; ++i) {
for (int j : h[i]) {
if (i > j) {
hl.ae(i, j);
}
}
}
hl.pre();
SegmentTree st = new SegmentTree(cols);
int[] ref = new int[cols];
Arrays.fill(ref, -1);
for (int i = 0; i < cols; ++i) {
ref[hl.id[i]] = i;
}
while (q-- > 0) {
int t = ni();
if (t == 1) {// modification query
int u = ni() - 1;
long v = ni();
u = col[u];
w[u].add(v);
st.setVal(hl.id[u], w[u].peek());
} else {// ouput query
int src = ni() - 1;
int dst = ni() - 1;
src = col[src];
dst = col[dst];
long v = output(src, dst, hl, st);
out.println(v == -1 ? v : v >> 32);
if (v != -1) {
w[ref[(int) v]].poll();
st.setVal((int) v, w[ref[(int) v]].peek());
}
}
}
}
long output(int a, int b, HLDecomposition hl, SegmentTree st) {
long ea = -1;
long eb = -1;
while (hl.head[a] != hl.head[b]) {
if (hl.depth[hl.head[a]] < hl.depth[hl.head[b]]) {
int tmp = a;
a = b;
b = tmp;
long tmp_e = ea;
ea = eb;
eb = tmp_e;
}
ea = merge(st.query(hl.id[hl.head[a]], hl.id[a] + 1), ea);
a = hl.parent[hl.head[a]];
}
if (hl.depth[a] < hl.depth[b]) {
int tmp = a;
a = b;
b = tmp;
long tmp_e = ea;
ea = eb;
eb = tmp_e;
}
return merge(eb, merge(st.query(hl.id[b], hl.id[a] + 1), ea));
}
long merge(long a, long b) {
return Math.max(a, b);
}
class SegmentTree {
int n;
long[] Vs;
public SegmentTree(int n_) {
n = 1;
while (n < n_) {
n *= 2;
}
Vs = new long[2 * n - 1];
for (int i = 0; i < n; ++i) {
Vs[i + n - 1] = -1;
}
for (int i = n - 2; i >= 0; --i) {
Vs[i] = merge(Vs[2 * i + 1], Vs[2 * i + 2]);
}
}
void setVal(int k, long val) {
k += n - 1;
if (val != -1)
Vs[k] = val << 32 | (k - (n - 1));
else
Vs[k] = -1;
while (k > 0) {
k = (k - 1) / 2;
Vs[k] = merge(Vs[2 * k + 1], Vs[2 * k + 2]);
}
}
// [a,b),[l,r)
long query(int a, int b) {
return query(a, b, 0, n, 0);
}
long query(int a, int b, int l, int r, int k) {
if (b <= l || r <= a) {
return -1L;
}
if (a <= l && r <= b) {
return Vs[k];
} else {
long vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
long vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
return merge(vl, vr);
}
}
}
class HLDecomposition {
int n;
int[] depth;
int[] head;
int[] heavy;
int[] parent;
int[] sz;
ArrayList<Integer>[] g;
int[] id;
@SuppressWarnings("unchecked")
public HLDecomposition(int n) {
this.n = n;
depth = new int[n];
head = new int[n];
heavy = new int[n];
parent = new int[n];
id = new int[n];
sz = new int[n];
g = new ArrayList[n];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<>();
}
Arrays.fill(head, -1);
Arrays.fill(id, -1);
Arrays.fill(parent, -1);
}
void ae(int a, int b) {
g[a].add(b);
g[b].add(a);
}
void pre() {
dfs(0, -1);
bfs();
}
void bfs() {
ArrayDeque<Integer> pend = new ArrayDeque<>();
int gen = 0;
pend.add(0);
while (!pend.isEmpty()) {
int v = pend.pollFirst();
int top = v;
for (; v != -1; v = heavy[v]) {
id[v] = gen++;
head[v] = top;
for (int d : g[v]) {
if (d == parent[v] || d == heavy[v]) {
continue;
}
pend.add(d);
}
}
}
}
int lca(int u, int v) {
if (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) {
int tmp = u;
u = v;
v = tmp;
}
return lca(parent[head[u]], v);
} else {
if (depth[u] > depth[v]) {
int tmp = u;
u = v;
v = tmp;
}
return u;
}
}
int dfs(int c, int p) {
parent[c] = p;
int s = 1;
int to = -1;
for (int d : g[c]) {
if (d == p)
continue;
depth[d] = depth[c] + 1;
s += dfs(d, c);
if (to == -1 || sz[d] > sz[to]) {
to = d;
}
}
sz[c] = s;
heavy[c] = to;
return s;
}
}
class Scanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
public int nextInt() {
return (int) nextLong();
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
void run() throws Exception {
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!INPUT.isEmpty())
tr(System.currentTimeMillis() - s + "ms");
// Thread t = new Thread(null, null, "~",
// Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
public static void main(String[] args) throws Exception {
new Main().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nl();
return a;
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m) {
int[][] map = new int[n][];
for (int i = 0; i < n; i++)
map[i] = na(m);
return map;
}
private int ni() {
return (int) nl();
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) {
System.out.println(Arrays.deepToString(o));
}
}