【CodeForces】CodeForces Round #483 (Div. 1 + Div. 2) 題解

【比賽連結】

Div. 1

Div. 2

【題解連結】

點選打開連結

【Div.2 A】Game

【思路要點】

排序，取中位數為答案。

時間複雜度\(O(NLogN)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int a[MAXN];
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	sort(a + 1, a + n + 1);
	printf("%d\n", a[(n + 1) / 2]);
	return 0;
}

【Div.2 B】Minesweeper

【思路要點】

模拟題意檢驗即可。

時間複雜度\(O(N*M)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[8] = {-1, 1, -1, 1, 0, -1, 1, 0};
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m;
char mp[MAXN][MAXN];
int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++)
		scanf("\n%s", mp[i] + 1);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
		if (mp[i][j] == '*') continue;
		int cnt = 0;
		if (mp[i][j] != '.') cnt = mp[i][j] - '0';
		for (int k = 0; k < 8; k++)
			if (mp[i + dx[k]][j + dy[k]] == '*') cnt--;
		if (cnt != 0) {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

【Div.2 C/Div.1 A】Finite or not?

【思路要點】

令\(q'=\frac{q}{gcd(p,q)}\)，問題等價于詢問\(\frac{b^{\infty}}{q'}\)是不是整數。

不斷地取\(g=gcd(q',b)\)，并令\(q'=\frac{q'}{g}\)，直到\(g=1\)為止。

檢查是否有\(q'=1\)即可回答詢問。

由于\(q'\)至多減少\(O(LogV)\)次，該做法的時間複雜度為\(O(NLog^2V)\)，可能無法通過1s的時限。

注意到我們可以取\(g=gcd(q',g)\)，得到的\(g\)是相同的。

而\(g\)至多減少\(O(LogV)\)次，每次減少會對時間複雜度産生\(O(1)\)的貢獻，是以求解gcd的總時間複雜度降至\(O(NLogV)\)，總體時間複雜度\(O(NLogV)\)，可以通過本題。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
long long gcd(long long x, long long y) {
	if (y == 0) return x;
	else return gcd(y, x % y);
}
int main() {
	int n; read(n);
	while (n--) {
		long long a, b, c;
		read(a), read(b), read(c);
		if (a % b == 0) printf("Finite\n");
		else {
			long long g = gcd(a, b);
			b /= g; g = gcd(b, c);
			for (int i = 1; i <= 64; i++) {
				g = gcd(b, g);
				b /= g;
			}
			if (b == 1) printf("Finite\n");
			else printf("Infinite\n");
		}
	}
	return 0;
}

【Div.2 D/Div.1 B】XOR-pyramid

【思路要點】

由題，令\(val_{i,j}\)為\(f(a_i,a_{i+1},...,a_j)\)的值。

則當\(i<j\)，顯然有\(val_{i,j}=val_{i,j-1}\ xor\ val_{i+1,j}\)。

預處理所有區間的\(val\)值，并DP求出區間内的最大值即可\(O(1)\)回答詢問。

時間複雜度\(O(N^2+Q)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int a[MAXN], f[MAXN][MAXN], ans[MAXN][MAXN];
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]), f[i][i] = a[i], ans[i][i] = a[i];
	for (int len = 2; len <= n; len++)
	for (int i = 1, j = len; j <= n; i++, j++) {
		f[i][j] = f[i + 1][j] ^ f[i][j - 1];
		ans[i][j] = f[i][j];
		chkmax(ans[i][j], ans[i + 1][j]);
		chkmax(ans[i][j], ans[i][j - 1]);
	}
	int q; read(q);
	while (q--) {
		int l, r;
		read(l), read(r);
		writeln(ans[l][r]);
	}
	return 0;
}

【Div.2 E/Div.1 C】Elevator

【思路要點】

考慮如何描述一個狀态：我們需要記錄目前已經接上過電梯的人數，電梯中存在的人所要去的樓層，以及電梯目前所在的樓層。

已經接上過電梯的人數是\(O(N)\)級别的，電梯目前所在的樓層共有9種。

由于電梯中的人數至多是4，如果我們認為空着的位置想要去的樓層為0，并保證這4個數有序，那麼可能的狀态共有\(\binom{13}{4}=715\)種。

通過适當地預處理，不難做到\(O(1)\)轉移。

注意到所有轉移的代價均為1，我們可以用BFS實作這個DP。

時間複雜度\(O(9*715*N)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXLOG = 61;
const int MAXP = 1e7 + 5;
const long long INF = 9e18;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct SegmentTree {
	struct Node {
		int lc, rc;
		int sum;
	} a[MAXP];
	int root, size;
	void insert(int &root, int depth, long long x, int d) {
		if (root == 0) root = ++size;
		a[root].sum += d;
		if (depth == -1) return;
		long long tmp = 1ll << depth;
		if (tmp & x) insert(a[root].rc, depth - 1, x, d);
		else insert(a[root].lc, depth - 1, x, d);
	}
	void insert(long long x, int d) {
		insert(root, MAXLOG, x, d);
	}
	long long query(int root, int depth, long long x, bool type) {
		if (depth == -1) return 0;
		long long tmp = 1ll << depth;
		if (type) {
			if (x & tmp) {
				if (a[a[root].rc].sum) return query(a[root].rc, depth - 1, x, type) + tmp;
				else return query(a[root].lc, depth - 1, x, type);
			} else {
				if (a[a[root].lc].sum) return query(a[root].lc, depth - 1, x, type);
				else return query(a[root].rc, depth - 1, x, type) + tmp;
			}
		} else {
			if (x & tmp) {
				if (a[a[root].lc].sum) return query(a[root].lc, depth - 1, x, type);
				else return -INF;
			} else {
				if (a[a[root].lc].sum) {
					long long tnp = query(a[root].lc, depth - 1, x, type);
					if (tnp > 0) return tnp;
				}
				if (a[a[root].rc].sum) return query(a[root].rc, depth - 1, x, true) + tmp;
				else return -INF;
			}
		}
	}
	long long query(long long x) {
		long long ans = query(root, MAXLOG, x, false);
		if (ans > 0) insert(ans, -1);
		return ans;
	}
} ST;
long long ans[MAXN];
int main() {
	int n; read(n);
	long long now = 0;
	for (int i = 1; i <= n; i++) {
		long long x; read(x);
		ST.insert(x, 1);
	}
	for (int i = 1; i <= n; i++) {
		long long tmp = ST.query(now);
		if (tmp <= 0) {
			printf("No\n");
			return 0;
		}
		now ^= tmp;
		ans[i] = tmp;
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++)
		write(ans[i]), putchar(' ');
	return 0;
}

【Div.1 D】Arkady and Rectangles

【思路要點】

對坐标離散化，使得坐标在\(O(N)\)的範圍内。

對X軸進行掃描線，并用線段樹維護Y軸。

我們希望線上段樹上維護資訊\(Max\)，在區間内可見且未被加入答案的，最大的顔色，若不存在，記-1。

如果我們能夠維護這一資訊，那麼我們隻需要不斷地将該值加入答案，直到其為-1即可。

為此，我們需要額外維護以下資訊：

\(Colours\)，定位到目前節點的顔色集合。

\(Min\)，區間内可見的最小顔色（包括0也考慮在内）。

更新時：

記子樹中\(Max\)的最大值為\(Childmax\)，子樹中\(Min\)的最小值為\(Childmin\)，\(Colours\)中最大值為\(Cmax\)。

若\(Colours\)不為空，且\(Cmax>Childmax\)，

那麼表示該區間被整個覆寫為了\(Cmax\)并且子樹中的未被加入答案的顔色因為這一次覆寫全部不可見，是以當\(Cmax\)已經在答案中出現，或是\(Childmin>Cmax\)（也即該區間已經被标号更靠後的顔色完全覆寫），\(Max=-1\)，否則\(Max=Cmax\)。

否則，也即\(Cmax≤Childmax\)，\(Max=Childmax\)。

若\(Colours\)不為空且\(Cmax>Childmin\)，\(Min=Cmax\)。

否則，\(Min=Childmin\)。

時間複雜度\(O(NLog^2N)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXP = 400005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct Heap {
	priority_queue <int> Main, Delt;
	void push(int x) {Main.push(x); }
	void delt(int x) {Delt.push(x); }
	int query() {
		while (!Delt.empty() && Main.top() == Delt.top()) {
			Main.pop();
			Delt.pop();
		}
		if (Main.empty()) return -1;
		else return Main.top();
	}
};
struct SegmentTree {
	struct Node {
		Heap heap;
		int Max, Min, lc, rc;
	} a[MAXP];
	int n, root, size;
	bool ans[MAXN];
	void build(int &root, int l, int r) {
		root = ++size;
		a[root].Max = -1;
		a[root].Min = 0;
		if (l == r) return;
		int mid = (l + r) / 2;
		build(a[root].lc, l, mid);
		build(a[root].rc, mid + 1, r);
	}
	void init(int x) {
		n = x;
		root = size = 0;
		build(root, 1, n);
	}
	void update(int root) {
		int col = a[root].heap.query();
		if (a[root].lc == 0) {
			if (col != -1 && !ans[col]) a[root].Max = col;
			else a[root].Max = -1;
			if (col != -1) a[root].Min = col;
			else a[root].Min = 0;
		} else {
			int childmax = max(a[a[root].lc].Max, a[a[root].rc].Max);
			int childmin = min(a[a[root].lc].Min, a[a[root].rc].Min);
			if (col != -1 && col > childmax) {
				if (ans[col] || col < childmin) a[root].Max = -1;
				else a[root].Max = col;
			} else a[root].Max = childmax;
			if (col != -1) a[root].Min = max(col, childmin);
			else a[root].Min = childmin;
		}
	}
	void insert(int root, int l, int r, int ql, int qr, int val) {
		if (l == ql && r == qr) {
			a[root].heap.push(val);
			update(root);
			return;
		}
		int mid = (l + r) / 2;
		if (mid >= ql) insert(a[root].lc, l, mid, ql, min(mid, qr), val);
		if (mid + 1 <= qr) insert(a[root].rc, mid + 1, r, max(mid + 1, ql), qr, val);
		update(root);
	}
	void insert(int l, int r, int val) {
		insert(root, 1, n, l, r, val);
	}
	void delt(int root, int l, int r, int ql, int qr, int val) {
		if (l == ql && r == qr) {
			a[root].heap.delt(val);
			update(root);
			return;
		}
		int mid = (l + r) / 2;
		if (mid >= ql) delt(a[root].lc, l, mid, ql, min(mid, qr), val);
		if (mid + 1 <= qr) delt(a[root].rc, mid + 1, r, max(mid + 1, ql), qr, val);
		update(root);
	}
	void delt(int l, int r, int val) {
		delt(root, 1, n, l, r, val);
	}
	void maintain(int root, int l, int r, int tmp) {
		if (a[root].Max != tmp) return;
		if (l == r) {
			update(root);
			return;
		}
		int mid = (l + r) / 2;
		maintain(a[root].lc, l, mid, tmp);
		maintain(a[root].rc, mid + 1, r, tmp);
		update(root);
	}
	void maintain() {
		while (a[root].Max != -1) {
			int tmp = a[root].Max;
			ans[tmp] = true;
			maintain(root, 1, n, tmp);
		}
	}
	int query(int n) {
		int sum = 1;
		for (int i = 1; i <= n; i++)
			sum += ans[i];
		return sum;
	}
} ST;
vector <int> l[MAXN], r[MAXN], val[MAXN];
int n, xl[MAXN], xr[MAXN], yl[MAXN], yr[MAXN];
int xn, ym, top, tmp[MAXN];
int main() {
	read(n);
	top = 0;
	for (int i = 1; i <= n; i++) {
		read(xl[i]), read(yl[i]);
		read(xr[i]), read(yr[i]);
		tmp[++top] = xl[i];
		tmp[++top] = xr[i];
	}
	sort(tmp + 1, tmp + top + 1);
	xn = top = unique(tmp + 1, tmp + top + 1) - tmp - 1;
	for (int i = 1; i <= n; i++) {
		xl[i] = lower_bound(tmp + 1, tmp + top + 1, xl[i]) - tmp;
		xr[i] = lower_bound(tmp + 1, tmp + top + 1, xr[i]) - tmp;
	}
	top = 0;
	for (int i = 1; i <= n; i++) {
		tmp[++top] = yl[i];
		tmp[++top] = yr[i];
	}
	sort(tmp + 1, tmp + top + 1);
	ym = top = unique(tmp + 1, tmp + top + 1) - tmp - 1;
	for (int i = 1; i <= n; i++) {
		yl[i] = lower_bound(tmp + 1, tmp + top + 1, yl[i]) - tmp;
		yr[i] = lower_bound(tmp + 1, tmp + top + 1, yr[i]) - tmp;
	}
	ST.init(ym - 1);
	for (int i = 1; i <= n; i++) {
		l[xl[i]].push_back(yl[i]);
		r[xl[i]].push_back(yr[i] - 1);
		val[xl[i]].push_back(i);
		l[xr[i]].push_back(yl[i]);
		r[xr[i]].push_back(yr[i] - 1);
		val[xr[i]].push_back(-i);
	}
	for (int i = 1; i <= xn; i++) {
		for (unsigned j = 0; j < l[i].size(); j++)
			if (val[i][j] > 0) ST.insert(l[i][j], r[i][j], val[i][j]);
			else ST.delt(l[i][j], r[i][j], -val[i][j]);
		ST.maintain();
	}
	writeln(ST.query(n));
	return 0;
}

【Div.1 E】NN country

【思路要點】

考慮一個詢問\((x,y)\)，令\(z=lca(x,y)\)。

若詢問\((x,z)\)的答案為\(a\)，詢問\((y,z)\)的答案為\(b\)，那麼詢問\((x,y)\)的答案或為\(a+b\)，或為\(a+b-1\)。

先考慮如何快速求出\(a\)和\(b\)。

考慮詢問\((x,z)\)，我們貪心地向上走到\(x\)可以到達的最靠近根的點，重複這個過程直到目前點深度小于\(z\)的深度即可。

預處理出每個點向上可以走到的最靠近根的點\(low_i\)，然後倍增預處理，即可在\(O(LogN)\)的時間内求出\(a\)和\(b\)。

現在我們考慮确定一個詢問的答案是\(a+b\)還是\(a+b-1\)。

令\(x\)向上走\(a-1\)步能夠走到的最靠近根的點為\(tx\)，\(y\)向上走\(b-1\)步能夠走到的最靠近根的點為\(ty\)，當且僅當\(tx\)與\(ty\)可以互相直接到達，答案為\(a+b-1\)。

\(tx\)與\(ty\)可以互相直接到達等價于存在一條線路使得其兩端分别在\(tx\)和\(ty\)的子樹内。

對樹進行DFS，每當遇到一個線路的端點，将其另一端對應的點權值+1，若開始通路\(tx\)和結束通路\(tx\)時，\(ty\)的子樹權值和不相同，則說明存在一條線路使得其兩端分别在\(tx\)和\(ty\)的子樹内，否則則不存在。

時間複雜度\(O(NLogN+MLogN+QLogN)\)。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXLOG = 20;
const int INF = 1e9;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct BinaryIndexTree {
	int n, a[MAXN];
	void init(int x) {
		n = x;
		memset(a, 0, sizeof(a));
	}
	void modify(int x, int d) {
		for (int i = x; i <= n; i += i & -i)
			a[i] += d;
	}
	int query(int l, int r) {
		int ans = 0;
		for (int i = r; i >= 1; i -= i & -i)
			ans += a[i];
		for (int i = l - 1; i >= 1; i -= i & -i)
			ans -= a[i];
		return ans;
	}
} BIT;
vector <int> a[MAXN], b[MAXN];
vector <int> pr[MAXN], home[MAXN], sum[MAXN];
int n, m, q, father[MAXN][MAXLOG], depth[MAXN];
int ans[MAXN], up[MAXN][MAXLOG];
int timer, dfn[MAXN], rit[MAXN];
void work(int pos) {
	for (unsigned i = 0; i < pr[pos].size(); i++)
		sum[pos].push_back(BIT.query(dfn[pr[pos][i]], rit[pr[pos][i]]));
	for (unsigned i = 0; i < b[pos].size(); i++)
		BIT.modify(dfn[b[pos][i]], 1);
	for (unsigned i = 0; i < a[pos].size(); i++)
		work(a[pos][i]);
	for (unsigned i = 0; i < pr[pos].size(); i++)
		if (sum[pos][i] != BIT.query(dfn[pr[pos][i]], rit[pr[pos][i]])) ans[home[pos][i]]--;
}
int steps(int pos, int dest) {
	if (pos == dest) return 0;
	int ans = 0;
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (up[pos][i] > dest) {
			pos = up[pos][i];
			ans += 1 << i;
		}
	if (up[pos][0] > dest) return INF;
	else return ans + 1;
}
int climb(int pos, int cnt) {
	for (int i = 0; i < MAXLOG; i++)
		if (cnt & (1 << i)) pos = up[pos][i];
	return pos;
}
void getup(int pos) {
	for (unsigned i = 0; i < a[pos].size(); i++) {
		getup(a[pos][i]);
		chkmin(up[pos][0], up[a[pos][i]][0]);
	}
}
int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (depth[father[x][i]] >= depth[y]) x = father[x][i];
	if (x == y) return x;
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (father[x][i] != father[y][i]) {
			x = father[x][i];
			y = father[y][i];
		}
	return father[x][0];
}
void dfs(int pos) {
	for (int i = 1; i < MAXLOG; i++)
		father[pos][i] = father[father[pos][i - 1]][i - 1];
	dfn[pos] = ++timer;
	for (unsigned i = 0; i < a[pos].size(); i++) {
		depth[a[pos][i]] = depth[pos] + 1;
		dfs(a[pos][i]);
	}
	rit[pos] = timer;
}
int main() {
	read(n);
	for (int i = 2; i <= n; i++) {
		read(father[i][0]);
		for (int j = 1; j < MAXLOG; j++)
			father[i][j] = father[father[i][j - 1]][j - 1];
		a[father[i][0]].push_back(i);
	}
	depth[1] = 1; dfs(1);
	read(m);
	for (int i = 1; i <= n; i++)
		up[i][0] = i;
	for (int i = 1; i <= m; i++) {
		int x, y; read(x), read(y);
		b[x].push_back(y);
		b[y].push_back(x);
		int z = lca(x, y);
		chkmin(up[x][0], z);
		chkmin(up[y][0], z);
	}
	getup(1);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j < MAXLOG; j++)
		up[i][j] = up[up[i][j - 1]][j - 1];
	read(q);
	for (int i = 1; i <= q; i++) {
		int x, y; read(x), read(y);
		int z = lca(x, y);
		if (z == x) ans[i] = steps(y, z);
		else if (z == y) ans[i] = steps(x, z);
		else {
			int cx = steps(x, z);
			int cy = steps(y, z);
			ans[i] = cx + cy;
			int tx = climb(x, cx - 1);
			int ty = climb(y, cy - 1);
			pr[tx].push_back(ty);
			home[tx].push_back(i);
		}
	}
	BIT.init(n);
	work(1);
	for (int i = 1; i <= q; i++)
		if (ans[i] >= INF) writeln(-1);
		else writeln(ans[i]);
	return 0;
}

【CodeForces】CodeForces Round #483 (Div. 1 + Div. 2) 題解

繼續閱讀

【CodeForces1153F】Serval and Bonus Problem

【CodeForces553E】Kyoya and Train

【CodeForces1202F】You Are Given Some Letters...

【BZOJ3534】【SDOI2014】重建

【LOJ2553】「CTSC2018」暴力寫挂

【LOJ6403】「ICPC World Finals 2018」趕飛機

【LOJ6406】「ICPC World Finals 2018」綠寶石之島

【校内訓練2019-03-22】禮物

【BZOJ3277】串

【BZOJ5205】【LOJ6301】「CodePlus 2018 3 月賽」白金元首與莫斯科

【LOJ2950】「NOIP2018」鋪設道路

【BZOJ4755】【JSOI2016】扭動的回文串

【BZOJ1337】最小圓覆寫

【BZOJ2002】【HNOI2010】Bounce 彈飛綿羊

【AtCoder】AtCoder Regular Contest 092 題解

【BZOJ2733】【HNOI2012】永無鄉