結果
問題 | No.1914 Directed by Two Sequences |
ユーザー |
|
提出日時 | 2025-05-20 12:20:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 351 ms / 3,000 ms |
コード長 | 4,302 bytes |
コンパイル時間 | 2,891 ms |
コンパイル使用メモリ | 224,360 KB |
実行使用メモリ | 60,824 KB |
最終ジャッジ日時 | 2025-05-20 12:20:42 |
合計ジャッジ時間 | 22,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; template<class T> void chkmn(T &x, T y) { if (y < x) x = y; } template<class T> void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 100010; int n, m, a[maxn], b[maxn], vis[maxn], rnk[maxn], idx[maxn], timer, col[maxn], tot, deg[maxn], od[maxn]; pii ed[maxn]; map<int, int> ban[maxn], rban[maxn]; map<pii, int> del; vector<int> vec[maxn], ade[maxn]; set<int> S; queue<int> q; struct segtree { #define mid ((l + r) >> 1) int t[maxn << 2]; void build(int c, int l, int r, int *a) { if (l == r) return t[c] = a[l], void(); build(c << 1, l, mid, a), build(c << 1 | 1, mid + 1, r, a); t[c] = max(t[c << 1], t[c << 1 | 1]); } void cg(int c, int l, int r, int x, int v) { if (l == r) return t[c] = v, void(); if (x <= mid) cg(c << 1, l, mid, x, v); else cg(c << 1 | 1, mid + 1, r, x, v); t[c] = max(t[c << 1], t[c << 1 | 1]); } int pre(int c, int l, int r, int x, int v) { if (l >= x || t[c] <= v) return 0; if (l == r) return l; int res = pre(c << 1 | 1, mid + 1, r, x, v); if (res >= 1) return res; return pre(c << 1, l, mid, x, v); } int suf(int c, int l, int r, int x, int v) { if (r <= x || t[c] <= v) return n + 1; if (l == r) return l; int res = suf(c << 1, l, mid, x, v); if (res <= n) return res; return suf(c << 1 | 1, mid + 1, r, x, v); } #undef mid } ta, tb; void dfs1(int x) { vis[x] = 1, ta.cg(1, 1, n, x, 0), tb.cg(1, 1, n, x, 0); int cur = x; while (cur <= n) { int pos = tb.suf(1, 1, n, cur, a[x]); if (pos > n) break; if (!ban[x][pos]) dfs1(pos); cur = pos; } cur = x; while (cur >= 1) { int pos = ta.pre(1, 1, n, cur, b[x]); if (pos < 1) break; if (!ban[x][pos]) dfs1(pos); cur = pos; } idx[x] = ++timer, rnk[timer] = x; } void dfs2(int x, int c) { vis[x] = 1, col[x] = c, ta.cg(1, 1, n, x, 0), tb.cg(1, 1, n, x, 0); int cur = x; while (cur <= n) { int pos = tb.suf(1, 1, n, cur, a[x]); if (pos > n) break; if (!rban[x][pos]) dfs2(pos, c); cur = pos; } cur = x; while (cur >= 1) { int pos = ta.pre(1, 1, n, cur, b[x]); if (pos < 1) break; if (!rban[x][pos]) dfs2(pos, c); cur = pos; } } bool check(int x, int y) { return 1ll * SZ(vec[x]) * SZ(vec[y]) > del[pii(x, y)]; } int main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); cin >> n >> m; rep (i, 1, n) cin >> a[i]; rep (i, 1, n) cin >> b[i]; rep (i, 1, m) { int u, v; cin >> u >> v; if (u > v) swap(u, v); if (a[u] < b[v]) ban[u][v] = 1, rban[v][u] = 1, ed[i] = pii(u, v); else ban[v][u] = 1, rban[u][v] = 1, ed[i] = pii(v, u); } ta.build(1, 1, n, a), tb.build(1, 1, n, b); rep (i, 1, n) if (!vis[i]) dfs1(i); rep (i, 1, n) vis[i] = 0, a[i] = 2 * n - a[i] + 1, b[i] = 2 * n - b[i] + 1; ta.build(1, 1, n, a), tb.build(1, 1, n, b); per (i, n, 1) if (!vis[rnk[i]]) dfs2(rnk[i], ++tot); rep (i, 1, n) vec[col[i]].emplace_back(i); rep (i, 1, m) { int u = ed[i].fi, v = ed[i].se; if (col[u] == col[v]) continue; if (col[u] > col[v]) swap(u, v); del[pii(col[u], col[v])]++; } per (i, tot, 1) { while (!q.empty()) q.pop(); for (int x : S) q.emplace(x); vector<int> opt; while (!q.empty()) { int u = q.front(); q.pop(); if (check(i, u)) { deg[u]++, ade[i].emplace_back(u); if (od[u]) S.erase(u), od[u] = 0; } else { for (int v : ade[u]) { opt.emplace_back(v); if (!--deg[v]) q.emplace(v); } } } S.insert(i), od[i] = 1; for (int x : opt) deg[x]++; } int sum = 0; rep (i, 1, tot) if (SZ(vec[i]) > 1) sum += SZ(vec[i]); rep (i, 1, tot) sum += SZ(ade[i]); cout << sum << '\n'; rep (i, 1, tot) if (SZ(vec[i]) > 1) { rep (j, 0, SZ(vec[i]) - 1) cout << vec[i][j] << ' ' << vec[i][(j + 1) % SZ(vec[i])] << '\n'; } rep (i, 1, tot) for (int j : ade[i]) cout << vec[i][0] << ' ' << vec[j][0] << '\n'; }