結果

問題 No.1914 Directed by Two Sequences
ユーザー Zhang Letao
提出日時 2025-05-24 16:39:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 782 ms / 3,000 ms
コード長 4,386 bytes
コンパイル時間 2,980 ms
コンパイル使用メモリ 220,696 KB
実行使用メモリ 57,856 KB
最終ジャッジ日時 2025-05-24 16:39:37
合計ジャッジ時間 23,369 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:146:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  146 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:148:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |                 scanf("%d", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:151:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  151 |                 scanf("%d", &b[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:156:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  156 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 100100;

int n, m, a[maxn], b[maxn], at;
pii ans[maxn << 2];
vector<int> ban[maxn], vc[maxn], G2[maxn];
vector<pii> G1[maxn];

struct SGT1 {
	pii a[maxn * 3], b[maxn * 3];
	int N;
	
	inline void init(int *c) {
		N = 1;
		while (N < n + 2) {
			N <<= 1;
		}
		for (int i = 1; i <= n; ++i) {
			a[i + N] = b[i + N] = mkp(c[i], i);
		}
		for (int i = N - 1; i; --i) {
			a[i] = min(a[i << 1], a[i << 1 | 1]);
			b[i] = max(b[i << 1], b[i << 1 | 1]);
		}
	}
	
	inline void update(int x) {
		x += N;
		a[x] = mkp(1e9, 0);
		b[x] = mkp(-1e9, 0);
		while (x >>= 1) {
			a[x] = min(a[x << 1], a[x << 1 | 1]);
			b[x] = max(b[x << 1], b[x << 1 | 1]);
		}
	}
	
	inline pii qmin(int l, int r) {
		pii res(1e9, 0);
		for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
			if (!(l & 1)) {
				res = min(res, a[l ^ 1]);
			}
			if (r & 1) {
				res = min(res, a[r ^ 1]);
			}
		}
		return res;
	}
	
	inline pii qmax(int l, int r) {
		pii res(-1e9, 0);
		for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
			if (!(l & 1)) {
				res = max(res, b[l ^ 1]);
			}
			if (r & 1) {
				res = max(res, b[r ^ 1]);
			}
		}
		return res;
	}
} T1, T2;

int stk[maxn], top, scc[maxn], cnt;
bool vis[maxn];

void dfs(int u) {
	T1.update(u);
	T2.update(u);
	vis[u] = 1;
	for (pii p : G1[u]) {
		int l = p.fst, r = p.scd;
		if (u < l) {
			while (1) {
				pii p = T2.qmax(l, r);
				if (a[u] < p.fst) {
					dfs(p.scd);
				} else {
					break;
				}
			}
		} else {
			while (1) {
				pii p = T1.qmax(l, r);
				if (b[u] < p.fst) {
					dfs(p.scd);
				} else {
					break;
				}
			}
		}
	}
	stk[++top] = u;
}

void dfs2(int u) {
	T1.update(u);
	T2.update(u);
	scc[u] = cnt;
	vc[cnt].pb(u);
	for (pii p : G1[u]) {
		int l = p.fst, r = p.scd;
		if (u < l) {
			while (1) {
				pii p = T2.qmin(l, r);
				if (a[u] > p.fst) {
					dfs2(p.scd);
				} else {
					break;
				}
			}
		} else {
			while (1) {
				pii p = T1.qmin(l, r);
				if (b[u] > p.fst) {
					dfs2(p.scd);
				} else {
					break;
				}
			}
		}
	}
}

int ind[maxn], nd[maxn];
map<pii, int> mp;

inline bool check(int u, int v) {
	return 1LL * ((ll)vc[u].size()) * ((ll)vc[v].size()) - mp[mkp(u, v)] > 0;
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
		ban[i].pb(i);
	}
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		ban[u].pb(v);
		ban[v].pb(u);
	}
	for (int i = 1; i <= n; ++i) {
		sort(ban[i].begin(), ban[i].end());
		int lst = 1;
		for (int j : ban[i]) {
			if (lst < j) {
				G1[i].pb(lst, j - 1);
			}
			lst = j + 1;
		}
		if (lst <= n) {
			G1[i].pb(lst, n);
		}
	}
	T1.init(a);
	T2.init(b);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	T1.init(a);
	T2.init(b);
	for (int i = n; i; --i) {
		int u = stk[i];
		if (!scc[u]) {
			++cnt;
			dfs2(u);
			if ((int)vc[cnt].size() >= 2) {
				for (int j = 0; j + 1 < (int)vc[cnt].size(); ++j) {
					ans[++at] = mkp(vc[cnt][j], vc[cnt][j + 1]);
				}
				ans[++at] = mkp(vc[cnt].back(), vc[cnt][0]);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j : ban[i]) {
			if (i == j) {
				continue;
			}
			int x = scc[i], y = scc[j];
			if (x < y) {
				++mp[mkp(x, y)];
			}
		}
	}
	vector<int> V;
	V.pb(cnt);
	for (int i = cnt - 1; i; --i) {
		for (int u = 1; u <= cnt; ++u) {
			nd[u] = ind[u];
		}
		queue<int> q;
		for (int u : V) {
			if (!nd[u]) {
				q.push(u);
			}
		}
		vector<int>().swap(V);
		int tt = 0;
		while (q.size()) {
			int u = q.front();
			q.pop();
			if (!ind[u]) {
				V.pb(u);
			}
			if (check(i, u)) {
				G2[i].pb(u);
				ans[++at] = mkp(vc[i][0], vc[u][0]);
				++ind[u];
				a[++tt] = u;
			} else {
				for (int v : G2[u]) {
					a[++tt] = v;
					if (!(--nd[v])) {
						q.push(v);
					}
				}
			}
		}
		for (int j = 1; j <= tt; ++j) {
			int u = a[j];
			nd[u] = ind[u];
		}
		V.pb(i);
	}
	printf("%d\n", at);
	for (int i = 1; i <= at; ++i) {
		printf("%d %d\n", ans[i].fst, ans[i].scd);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
0