NJPC2017: F - ダブルス
問題概要
数直線の原点上に人が2人いる。時刻Tiに座標Xiへボールが飛んでくることを意味するN個の整数の組(Ti, Xi)が与えられる。このとき2人のうちどちらか一人が時刻Tiに座標Xiにいるとボールをキャッチすることができる。2人の移動速度をvとしたとき、すべてのボールをキャッチできる最小のvを求めよ。
N <= 105
解法
二分探索をし、二分探索の中でDPをする。i個目のボールを処理した時点で、ボールをキャッチした方の人はXiにいて、キャッチしてない方の人はある連続した区間内のどこかにいる。この区間がなるべく広くなるようキャッチの担当を割り当てた方が得であるので、以下のようなDPが立つ。
dp(i): ボールiまでを処理したとき、ボールiをキャッチしていない方の人が存在しうる最大の区間
遷移は「i個目のボールをキャッチした人が(i+1)個目もキャッチする」「i個目のボールをキャッチしなかった人が(i+1)個目をキャッチする」の2通り。ボールをキャッチしに行く人が間に合うかどうかは、二分探索で速度を決め打っていることから計算可能である。ボールをキャッチしない方の人はその分左右に膨らむことができるのでそれに基づいて区間を求める。
感想
区間が連続になる が本質っぽい(むずい)
コード (D言語)
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; void main() { immutable real INF = 1L << 59; auto N = readln.chomp.to!int; auto T = new long[](N); auto X = new long[](N); foreach (i; 0..N) { auto s = readln.split.map!(to!long); T[i] = s[0]; X[i] = s[1]; } real hi = 10^^9; real lo = 0; foreach (_; 0..100) { real mid = (hi + lo) / 2; auto dp = new Tuple!(real, real)[](N+1); foreach (i; 0..N+1) dp[i] = tuple(INF, -INF); dp[0] = tuple(0.0L, 0.0L); real prev_t = 0; real prev_x = 0; foreach (i; 0..N) { if (dp[i][0] > dp[i][1]) break; real t = T[i] - prev_t; real x = abs(X[i] - prev_x); if (x <= mid * t) { dp[i+1][0] = min(dp[i+1][0], dp[i][0] - t * mid); dp[i+1][1] = max(dp[i+1][1], dp[i][1] + t * mid); } if (dp[i][0] - t * mid <= X[i] && X[i] <= dp[i][1] + t * mid) { dp[i+1][0] = min(dp[i+1][0], prev_x - t * mid); dp[i+1][1] = max(dp[i+1][1], prev_x + t * mid); } prev_t = T[i]; prev_x = X[i]; } (dp[N][0] <= dp[N][1] ? hi : lo) = mid; } writefln("%.09f", hi); }
AtCoder Regular Contest 097: E - Sorted and Sorted
https://beta.atcoder.jp/contests/arc097/tasks/arc097_c
問題概要
1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たときその色のボールが番号の小さい順に左から並んでいる状態にしたい。この状態を達成するための最小操作回数を求めよ。
解法
左から順番にボールを確定させていくことを考える。まず一番左に置けるのは黒1か白1のどちらかである。ここで仮に黒1を置いた場合、その次に置けるのは黒2か白1である。このように次に使えるボールは常に「黒・白それぞれの使ってないボールの中で最も若い番号のもの」ということになる。よって以下のような状態数N*NのDPが立つ。
dp(b, w): 黒のボールを番号b, 白のボールを番号wまで置いたときの最小操作回数
このDPの遷移は上で述べた通り2通り(次にb+1を置くかw+1を置くか)しかない。よってあとはこの遷移のための最小操作回数が高速にわかればこの問題が解けることになる。ここでその最小操作回数は「これから置くボールより初期位置が左にあって、かつまだ使われていないボールの数」に等しい。これは実は前計算しておくとO(1)で求まる。具体的には(b, w)の状態から次に黒(b+1)を置くとき、まだ使われていないボールというのは黒の(b+2)以上か白の(w+1)以上のボールである。これを満たすボールが自分より左に何個あるかがわかればよく、これは色ごとに累積和を取っておけばO(1)で参照することができる。
dp2(c, i, j): 色がcで番号がi以上のボールが、左からj番目までに何個出現するか
これはO(N2)で求められる。あとはO(N2)でDPを回しつつ遷移の際にこの累積和テーブルを参照して更新を行っていくと答えが求まる。
感想
こういうDPを本番に通せるようになってきてうれしいですね
コード (D言語)
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, std.regex; void main() { immutable int INF = 1 << 29; auto N = readln.chomp.to!int; auto A = new int[](2*N); auto C = new bool[](2*N); foreach (i; 0..2*N) { auto s = readln.split; A[i] = s[1].to!int; C[i] = s[0] == "B"; } auto BR = new int[](N+1); auto WR = new int[](N+1); foreach (i; 0..2*N) { if (C[i]) BR[A[i]] = i; else WR[A[i]] = i; } auto dpB = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいBの数 auto dpW = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいWの数 foreach (i; 0..N+1) foreach (j; 0..2*N) dpB[i][j+1] = dpB[i][j] + (C[j] && A[j] > i); foreach (i; 0..N+1) foreach (j; 0..2*N) dpW[i][j+1] = dpW[i][j] + (!C[j] && A[j] > i); auto dp = new int[][](N+1, N+1); foreach (i; 0..N+1) dp[i].fill(INF); dp[0][0] = 0; foreach (n; 1..2*N+1) { foreach (b; 0..n+1) { int w = n - b; if (b > N || w > N) { continue; } if (b > 0) { dp[b][w] = min(dp[b][w], dp[b-1][w] + dpB[b][BR[b]+1] + dpW[w][BR[b]+1]); } if (w > 0) { dp[b][w] = min(dp[b][w], dp[b][w-1] + dpW[w][WR[w]+1] + dpB[b][WR[w]+1]); } } } dp[N][N].writeln; }
第2回 ドワンゴからの挑戦状 予選: C - メンテナンス明け
https://beta.atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_c
問題概要
N個の駅とM個の路線が与えられる。各路線はLi個の駅を順につないだ単純パスになっており、各辺に移動時間が設定されている。駅srcから駅dstに向かいたいが、一度だけ寝過ごす可能性があり、寝過ごした場合は路線の終点まで強制的に移動する。一度寝過ごしたあとは二度と寝過ごすことはない。寝過ごしが任意の移動時に起こりうるとき、最大の移動時間を最小化するように移動したい。そのような場合の移動時間を求めよ。
N <= 25252
各路線に含まれる駅数の和 <= 252525
解法
二分探索をする。
- 必要な考察1. 仮に寝過ごしが発生した場合、寝過ごし後にたどり着く終点からdstまでは最小移動時間で行ける。またその最小移動時間はdstを始点にして1回ダイクストラを回せばすべての頂点に対して計算可能である。
- 必要な考察2. まだ寝過ごしが発生していない状態である辺を使って移動するとき、「仮にその移動で寝過ごしが発生した場合のdstまでの移動時間」は考察1より確定できる。
ここで「使っていい時間の最大値」を定めると、「もしある辺を使った移動で寝過ごしが起きたとき、移動時間が設定した最大値を超えるならばその辺を使うことはできない」ということが言える。よって二分探索の各ループではsrcから普通にダイクストラを回しつつ上の方法で禁止されない辺だけを使って移動していき、最終的にdstにたどり着けるかを見ればよい。
感想
あーすごい、こうやるのかというかんじ
コード (D言語)
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; void main() { immutable long INF = 1L << 59; auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto S = s[2]; auto T = s[3]; auto L = new int[](M); auto A = new int[][](M); auto W = new long[][](M); auto G = new Tuple!(int, long, int, long)[][](N); foreach (i; 0..M) { L[i] = readln.chomp.to!int; A[i] = readln.split.map!(to!int).array; W[i] = readln.split.map!(to!long).array; long acm1 = W[i].sum; long acm2 = 0; foreach (j; 0..L[i]-1) { acm2 += W[i][j]; G[A[i][j]] ~= tuple(A[i][j+1], W[i][j], A[i].back, acm1); G[A[i][j+1]] ~= tuple(A[i][j], W[i][j], A[i].front, acm2); acm1 -= W[i][j]; } } auto shortest = new long[](N); shortest.fill(INF); auto pq = new BinaryHeap!(Array!(Tuple!(int, long)), "a[1] > b[1]")(); auto dist = new long[](N); pq.insert(tuple(T, 0L)); while (!pq.empty) { auto t = pq.front; auto n = t[0]; auto d = t[1]; pq.removeFront; if (shortest[n] <= d) continue; shortest[n] = d; foreach (to; G[n]) { auto nn = to[0]; auto nd = d + to[1]; if (shortest[nn] <= nd) continue; pq.insert(tuple(nn, nd)); } } long hi = 10L^^15; long lo = 0; while (hi - lo > 1) { long mid = (hi + lo) / 2; dist.fill(INF); pq.clear(); pq.insert(tuple(S, 0L)); bool ok = false; while (!pq.empty) { auto t = pq.front; auto n = t[0]; auto d = t[1]; pq.removeFront; if (n == T) { ok = true; break; } if (dist[n] <= d) continue; dist[n] = d; foreach (to; G[n]) { auto nn = to[0]; auto nd = d + to[1]; auto zzz = to[2]; auto zzz_d = d + to[3]; if (zzz_d + shortest[zzz] > mid) continue; if (dist[nn] <= nd) continue; if (nd > mid) continue; pq.insert(tuple(nn, nd)); } } if (ok) hi = mid; else lo = mid; } hi.writeln; }
DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選: C - 特別講演「括弧列と塗り分け」
https://beta.atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c
問題概要
対応の取れた括弧列Sと非負整数Kが与えられる。Sの各文字を赤か青の2色で塗り分けるとき、すべての対応括弧の組(S[i], S[j])について、Sの区間[i, j]において赤と青の数の差がK以内になるような塗り方は何通りあるか。
|S|, K <= 3000
解法
木DPをした。括弧Aが括弧Bを包含しているときAがBの親となるようにすると、括弧の包含関係は木になる。また互いに包含関係にない括弧同士の塗り方は題意から独立である。このことから包含関係で木を作っていくと、1個以上の木(=森)ができる。それぞれの木でDPを行った結果を掛け合わせれば答えとなる。具体的なDPは
dp(n, k): 構築した森のノードnにあたる括弧(S[i], S[j])において、Sの区間[i, j]を赤と青の差がk以下になるよう塗る塗り方の総数
を順に各ノードでやっていくわけだが、これはまず子のDP値を全部求めた上でそれを使ってノード内でDPをすると求まる。
各ノードでO(NK2)?っぽいDPをやるので全部でO(N2 K2)かかりそうな気がするが、最大でも区間長×2の差しか生まれない(それ以上のkは見る必要がない)ことに気を付けて適切に枝刈りを入れるとオーダーが落ちて通る。こういう感じの木DPにおける典型知識らしい→参照: http://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594
感想
気を付けず適切に枝刈りを入れなかったのでTLEを出しまくった
コード (D言語)
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; void main() { immutable long MOD = 10^^9 + 7; auto S = readln.chomp; auto N = S.length.to!int; auto K = readln.chomp.to!int; K = min(K, 2*N); auto P = new Tuple!(int, int)[](N/2); auto G = new int[][](N/2); auto root = new bool[](N/2); root.fill(true); long inv2 = powmod(2, MOD-2, MOD); auto stack = new Tuple!(int, int)[](N/2); for (int i = 0, p = 0, sp = -1; i < N; ++i) { if (S[i] == '(') { if (sp >= 0) G[stack[sp][1]] ~= p, root[p] = false; stack[++sp] = tuple(i, p++); } else { P[stack[sp][1]] = tuple(stack[sp][0], i); sp--; } } auto dp = new long[][](N/2, K+1); auto tmp = new long[][](2, N+1); void dfs(int n) { foreach (m; G[n]) dfs(m); int M = P[n][1] - P[n][0] + 1; tmp[0].fill(0); tmp[1].fill(0); tmp[0][0] = 2; tmp[0][1] = 2; int cur = 0, tar = 1; foreach (m; G[n]) { tmp[tar].fill(0); for (int i = 0; i <= M; ++i) { if (tmp[cur][i] == 0) continue; for (int j = 0; j <= K/2 && i+j <= M && dp[m][j] > 0; ++j) { (tmp[tar][i+j] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD; } for (int j = 0; j <= K/2 && abs(i-j) <= M && dp[m][j] > 0; ++j) { (tmp[tar][abs(i-j)] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD; } } swap(cur, tar); } for (int i = 0; i <= K/2; ++i) dp[n][i] = tmp[cur][i]; } long ans = 1; foreach (i; 0..N/2) { if (!root[i]) continue; dfs(i); long t = 0; foreach (j; 0..K/2+1) t = (t + dp[i][j]) % MOD; ans = ans * t % MOD; } ans.writeln; } long powmod(long a, long x, long m) { long ret = 1; while (x) { if (x % 2) ret = ret * a % m; a = a * a % m; x /= 2; } return ret; }
第2回 ドワンゴからの挑戦状 本選: B - 道迷い
https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_b
問題概要
一次元上のN個の点を表す数列Xが与えられる。このうちのいずれかの点がオフィスだが、その点がオフィスであるかどうかは実際に訪れるまでわからない。ここで座標0からスタートし一定の速度vで一次元上を動き回るとき、どこにオフィスがあった場合でも必ずabs(Xi)以下の時間でオフィスにたどり着くようにしたい。最適な移動をしたとき取りうる最小の速度vを求めよ。
N <= 1000
abs(Xi) <= 109
解法
問題の二分探索臭がすごいので二分探索を考える。そうすると解くべき問題は「速度vを決め打つ。速度vで最適に動き回ったとき、Xのすべての点に時間abs(Xi)以下でたどり着くことは可能か」となる。ここで移動の特性を考えると
- 点aから点bに移動したときa-b間にある点はすべてついでに取れる
- このことから移動のパターンは「必ず外側が広がっていくようにジグザグに移動する」しかない(飛び地での移動も既に訪れた区間の内部をまた訪れるのも無意味)
ということがわかる。これを生かすと以下の区間DPが生える。
dp(i, j, left_or_right): 区間[X_i, X_j]を訪れていて、最後に訪れたのが(区間の左端or区間の右端)のときの、最小移動距離
上の特性からこのdpは外側に広がって区間を伸ばすような遷移しか考える必要がない。すなわち遷移は(左端or右端)×(左端or右端)の以下4パターンとなる。
- X_i -> X_{i-1} (左端から左に一個進む)
- X_i -> X_{j+1} (左端から右に折り返して右端を一個広げる)
- X_j -> X_{i-1} (右端から左に折り返して左端を一個広げる)
- X_j -> X_{j+1} (右端から右に一個進む)
遷移の際現在決め打っている速度で新たな点Xに時間abs(X)以内で到達できない場合は題意が満たされずその遷移は取れないのでスルーする。最後までDPを埋めたときdp(0, N-1)にちゃんと値が入っていればその速度はok, としてにぶたんを回していく。
感想
最後は必ず端っこで終わる→ひとつ前はその端っこの隣もしくは逆の端っこ→その繰り返し… となるとつまりジグザグが広がっていく形か~→それyukicoderでやったやつじゃんとなって区間DPが生えた。時間かかったけど通せて良かった~なお虚無の定数倍高速化(言語を変える)をまたやってしまいました
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; typedef long double ld; ll X[1010]; ll dp[1010][1010][2]; bool in_time(int i, long dist, ld vel) { return dist / vel <= abs(X[i]); } int main() { const ll INF = 1L << 59; int N; cin >> N; REP(i, N) cin >> X[i]; ld hi = 1000000000000000.0; ld lo = 1.0; REP(_, 100) { ld mid = (hi + lo) / 2; REP(i, N) REP(j, N) REP(k, 2) dp[i][j][k] = INF; REP(i, N) dp[i][i][0] = dp[i][i][1] = abs(X[i]); REP2 (len, 1, N+1) REP(l, N) REP(i, 2) REP(j, 2) { int r = l + len - 1; int nl = l; int nr = r; if (j == 0) nl -= 1; else nr += 1; if (nl < 0 || nr >= N) continue; if (i == 0 && j == 0) { ll nd = dp[l][r][i] + X[l] - X[nl]; if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 0 && j == 1) { ll nd = dp[l][r][i] + X[nr] - X[l]; if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 1 && j == 0) { ll nd = dp[l][r][i] + X[r] - X[nl]; if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 1 && j == 1) { ll nd = dp[l][r][i] + X[nr] - X[r]; if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } } if (min(dp[0][N-1][0], dp[0][N-1][1]) != INF) hi = mid; else lo = mid; } cout.precision(20); cout << fixed << hi << endl; }
第2回 ドワンゴからの挑戦状 本選: A - 通勤
https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_a
問題概要
ニコ数を「10進法で表記したとき各桁が2, 5のみからなり、かつどの隣り合う2桁の数字も相異なる数」と定義する。初め L=1, X=0 である。以下の2種類の操作を自由な順番で好きなだけ行ってXをNに一致させるとき、操作1を行う回数として最小のものを求めよ。
- 操作1: Lに任意のニコ数を掛ける
- 操作2: XにLを加算する。
N <= 10^{18}
解法
例えばN=123で、最初Lに5を掛ける場合を考える。いきなりLに5を掛けると、当然以降の加算は5の倍数刻みでしか行えなくなるため、X=123には永遠にたどりつけない。であるから、Lに5を掛ける前には、5で処理できない端数(123 % 5 = 3)をL=1の段階であらかじめ処理しておく必要がある。よってL=1を3回足してからLに5を掛けると、Nは残り120でL=5となる。実はこのとき両方をLで割って「Nは残り24でL=1」とみなしてしまって問題ない。このようにすると常にLが1に固定されてNがどんどんニコ数で割られていくという再帰的構造が現れるので、あとはメモ化再帰で解くことができる。Nが必ず2以上の数で割られるため状態数はそこまで増えない。
感想
再帰の構造を見出す部分がむじかった
コード (D言語)
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, std.regex; void main() { immutable long INF = 10L^18+10; auto N = readln.chomp.to!long; long[] nico; for (long a = 2; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a; for (long a = 5; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a; auto M = nico.length.to!int; long[long] mem; long dfs(long n) { if (n in mem) return mem[n]; if (n == 1) return 1; if (n == 0) return 0; long ret = INF; foreach (x; nico) ret = min(ret, dfs(n/x) + n%x); mem[n] = ret; return mem[n]; } dfs(N).writeln; }
yukicoder No.529 帰省ラッシュ
https://yukicoder.me/problems/no/529
問題概要
N頂点M辺の単純無向連結グラフとQ個のクエリが与えられる。クエリには以下の2種類が存在する。クエリを順に実行した結果を出力せよ。
- クエリ1. 頂点uに価値wの獲物が出現する
- クエリ2. 頂点sからtに、同じ辺を2度以上通らないように移動する。このとき通った頂点にいる獲物を1匹だけ獲得することができる。獲得価値が最大になるように移動し、そのときの獲得価値を求めよ。獲得した獲物は以後消滅する。
N <= 105
M, Q <= 2×105
現れる獲物の価値はすべて異なる
解法
- 二重辺連結成分分解をする
- HL分解をする
- s, tのLCAをuとしたとき、s-u, t-uの経路に含まれる最大値をセグ木とかで取る
まず「同じ辺を2度通らない」という条件から、s->tへ向かうときは無関係の橋を通ってはいけない(戻ってこれなくなるため)。逆にそれ以外の橋は必ず決まった順序で通る必要がある。また現在地から橋を通らないで行ける1頂点に寄ってから次の橋へ(あるいはtへ)行くという動きを必ず取ることができる。以上よりクエリ2は「グラフを二重辺連結成分分解する。sを含む連結成分->tを含む連結成分 の単純パス上にある連結成分に含まれる頂点から、もっとも価値の大きい獲物をとる」と言い換えることができる。この言い換えを採用するとクエリ1の獲物追加も頂点単位ではなく連結成分単位で管理すればよいことになる。
上のとおりに二十辺連結成分分解を導入した場合、クエリ2に答える手順は「分解後のグラフ上でs->tへの単純パスを求める→通った連結成分におけるmaxをとる→maxだった獲物を削除する」となる。これを愚直にやると毎回O(N)かかって間に合わない。計算量の削減のためには二十辺連結成分分解後のグラフが必ず木になっていること、ゆえにs->tへの単純パスはs, tそれぞれからLCA(s, t)に向かう単純パスをつないだものであることに注目する。このようなクエリにはHL分解が有効で、木のパスをうまいこと分けてセグ木等と組み合わせることでmaxをとる計算量を抑えることができる(HL分解についてすごくわかりやすかったページ→ http://math314.hateblo.jp/entry/2014/06/24/220107 )
感想
とにかく実装が大変で競プロでひとつの問題に対して書いたコードとしてはダントツの量になった 途中でかなり意味が分からなくなって俺はいったい何で何を分解して何を求めてるんだ…みたいな状態になりオギャ~~~~~だった
コード (D言語)
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; void dfs(int n, int p) { foreach (m; dfs_tree[n]) { if (m != p && ord[n] >= low[m]) { uf.unite(n, m); } dfs(m, n); } } dfs(0, -1); /* 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)); } }