結果

問題 No.1326 ふたりのDominator
コンテスト
ユーザー QCFium
提出日時 2020-12-02 22:30:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,291 bytes
コンパイル時間 2,206 ms
コンパイル使用メモリ 187,416 KB
実行使用メモリ 15,500 KB
最終ジャッジ日時 2024-09-23 02:52:28
合計ジャッジ時間 6,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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[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 i.r < j.r; });
		// init
		path.clear();
		l_ord = i[0].l;
		r_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