結果

問題 No.1914 Directed by Two Sequences
コンテスト
ユーザー Enucai
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0