結果

問題 No.1326 ふたりのDominator
ユーザー QCFiumQCFium
提出日時 2020-12-02 22:35:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,213 ms / 2,000 ms
コード長 4,316 bytes
コンパイル時間 2,104 ms
コンパイル使用メモリ 188,532 KB
実行使用メモリ 13,528 KB
最終ジャッジ日時 2024-09-23 02:53:16
合計ジャッジ時間 15,818 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 4 ms
6,940 KB
testcase_08 AC 5 ms
6,944 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 5 ms
6,940 KB
testcase_11 AC 5 ms
6,944 KB
testcase_12 AC 1,165 ms
10,120 KB
testcase_13 AC 1,148 ms
9,992 KB
testcase_14 AC 1,144 ms
10,124 KB
testcase_15 AC 1,157 ms
10,032 KB
testcase_16 AC 1,213 ms
9,980 KB
testcase_17 AC 1,194 ms
10,488 KB
testcase_18 AC 1,086 ms
12,288 KB
testcase_19 AC 939 ms
13,256 KB
testcase_20 AC 195 ms
11,724 KB
testcase_21 AC 502 ms
11,720 KB
testcase_22 AC 470 ms
13,528 KB
testcase_23 AC 977 ms
10,128 KB
testcase_24 AC 1,161 ms
9,992 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

std::vector<std::vector<int> > hen;

std::vector<int> ord, out;
std::vector<int> tour;
int ord_cnt = 0;
std::vector<int> low;
std::vector<int> depth;
std::vector<int> parent;

void dfs(int i, int prev) {
	parent[i] = prev;
	ord[i] = ord_cnt++;
	tour.push_back(i);
	low[i] = ord[i];
	for (auto j : hen[i]) {
		if (j == prev) continue;
		if (ord[j] == -1) {
			depth[j] = depth[i] + 1;
			dfs(j, i);
			low[i] = std::min(low[i], low[j]);
			ord_cnt++;
			tour.push_back(i);
		} else low[i] = std::min(low[i], ord[j]);
	}
	out[i] = ord_cnt;
}
bool is_ancestor(int i, int j) { // returns if i is a descendant of j
	return ord[i] >= ord[j] && out[i] <= out[j];
}

int main() {
	int n = ri();
	int m = ri();
	hen.resize(n);
	for (int i = 0; i < m; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	
	ord.resize(n, -1);
	out.resize(n, -1);
	low.resize(n);
	depth.resize(n);
	parent.resize(n);
	dfs(0, -1);
	
	std::deque<std::pair<int, bool> > path; // exclusive
	int l_ord = 0; // actual
	int r_ord = 0; // actual
	int cnt = 0;
	
	auto move_r_1 = [&] (int next_ord) {
		int l = tour[l_ord];
		int r = tour[r_ord];
		int next = tour[next_ord];
		if (l == r || r == next) {} // do nothing
		else if (next == parent[r] && !is_ancestor(l, r)) { // retract upwards
			if (path.size()) cnt -= path.back().second, path.pop_back();
		} else if (next != parent[r] && is_ancestor(l, r) && is_ancestor(l, next)) { // retract downwards
			if (path.size()) cnt -= path.back().second, path.pop_back();
		} else if (next == parent[r]) { // extend upwards
			int t = path.size() ? path.back().first : l;
			if (low[t] <= ord[next]) path.push_back({r, false}); // ok, false
			else path.push_back({r, true}), cnt++;
		} else if (is_ancestor(l, r)) { // first bent downwards extension
			int t1 = path.size() ? path.back().first : l;
			if (low[next] < ord[r] && low[t1] < ord[r]) path.push_back({r, false});
			else path.push_back({r, true}), cnt++;
		} else { // purely/bent extend downwards
			int t = path.size() ? path.back().first : l;
			if (low[next] <= ord[t]) path.push_back({r, false});
			else path.push_back({r, true}), cnt++;
		}
		r_ord = next_ord;
	};
	auto move_l_1 = [&] (int next_ord) {
		int l = tour[l_ord];
		int r = tour[r_ord];
		int next = tour[next_ord];
		if (l == r || r == next) {} // do nothing
		else if (next == parent[l] && !is_ancestor(r, l)) { // retract upwards
			if (path.size()) cnt -= path.front().second, path.pop_front();
		} else if (next != parent[l] && is_ancestor(r, l) && is_ancestor(r, next)) { // retract downwards
			if (path.size()) cnt -= path.front().second, path.pop_front();
		} else if (next == parent[l]) { // extend upwards
			int t = path.size() ? path.front().first : r;
			if (low[t] <= ord[next]) path.push_front({l, false}); // ok, false
			else path.push_front({l, true}), cnt++;
		} else if (is_ancestor(r, l)) { // first bent downwards extension
			int t1 = path.size() ? path.front().first : r;
			if (low[next] < ord[l] && low[t1] < ord[l]) path.push_front({l, false});
			else path.push_front({l, true}), cnt++;
		} else { // purely/bent extend downwards
			int t = path.size() ? path.front().first : r;
			if (low[next] <= ord[t]) path.push_front({l, false});
			else path.push_front({l, true}), cnt++;
		}
		l_ord = next_ord;
	};
	
	auto move_r_to = [&] (int i) {
		while (r_ord < ord[i]) move_r_1(r_ord + 1);
		while (r_ord > ord[i]) move_r_1(r_ord - 1);
	};
	auto move_l_to = [&] (int i) {
		while (l_ord < ord[i]) move_l_1(l_ord + 1);
		while (l_ord > ord[i]) move_l_1(l_ord - 1);
	};
	
	struct Query {
		int l;
		int r;
		int id;
	};
	
	int ONE = std::sqrt(ord_cnt);
	int BLOCK = (ord_cnt - 1) / ONE + 1;
	std::vector<Query> qs[BLOCK];
	
	int q = ri();
	for (int i = 0; i < q; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		qs[ord[a] / ONE].push_back({a, b, i});
	}
	int res[q];
	for (auto &i : qs) {
		if (!i.size()) continue;
		std::sort(i.begin(), i.end(), [] (auto &i, auto &j) { return ord[i.r] < ord[j.r]; });
		// init
		path.clear();
		l_ord = ord[i[0].l];
		r_ord = ord[i[0].l];
		cnt = 0;
		
		for (auto j : i) {
			move_l_to(j.l);
			move_r_to(j.r);
			res[j.id] = cnt;
		}
	}
	for (auto i : res) printf("%d\n", i);
	return 0;
}
0