#755678 (C++14) No.1914 Directed by Two Sequences

提出ソース

結果

問題	No.1914 Directed by Two Sequences
ユーザー	👑 hos.lyric
提出日時	2022-04-22 23:27:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	8,384 bytes
コンパイル時間	3,534 ms
コンパイル使用メモリ	168,696 KB
実行使用メモリ	814,280 KB
最終ジャッジ日時	2024-06-24 04:55:07
合計ジャッジ時間	12,999 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	63 ms 16,768 KB
testcase_03	AC	105 ms 22,536 KB
testcase_04	AC	89 ms 20,760 KB
testcase_05	AC	95 ms 21,348 KB
testcase_06	AC	81 ms 19,712 KB
testcase_07	AC	42 ms 11,392 KB
testcase_08	AC	48 ms 11,904 KB
testcase_09	AC	50 ms 12,288 KB
testcase_10	MLE	-
testcase_11	MLE	-
testcase_12	MLE	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


struct Scc {
  int n;
  vector<int> as, bs;
  vector<int> ptr, zu, us;

  int l;
  vector<int> ids;
  int operator[](int u) const { return ids[u]; }

  explicit Scc(int n_) : n(n_), as(), bs(), l(-1) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    as.push_back(u);
    bs.push_back(v);
  }

  void dfs0(int u) {
    if (!ids[u]) {
      ids[u] = -1;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs0(zu[i]);
      us.push_back(u);
    }
  }
  void dfs1(int u) {
    if (!~ids[u]) {
      ids[u] = l;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs1(zu[i]);
    }
  }
  void run() {
    const int m = as.size();
    ptr.resize(n + 2);
    zu.resize(m);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[as[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[as[i] + 1]++] = bs[i];
    ids.assign(n, 0);
    us.clear();
    for (int u = 0; u < n; ++u) dfs0(u);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[bs[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[bs[i] + 1]++] = as[i];
    l = 0;
    for (int j = n; --j >= 0; ) if (!~ids[us[j]]) { dfs1(us[j]); ++l; }
  }

  vector<vector<int>> group() const {
    assert(~l);
    vector<vector<int>> uss(l);
    for (int u = 0; u < n; ++u) uss[ids[u]].push_back(u);
    return uss;
  }
};

////////////////////////////////////////////////////////////////////////////////


vector<int> merge(const vector<int> &as, const vector<int> &bs) {
  vector<int> cs(as.size() + bs.size());
  std::merge(as.begin(), as.end(), bs.begin(), bs.end(), cs.begin());
  return cs;
}


int N, M;
vector<int> C, D;
vector<int> A, B;

vector<vector<int>> banCD, banDC;

int V;

struct Seg {
  int len;
  vector<int> us;
  vector<int> seg;
  void build() {
    len = us.size();
    seg.assign(len << 1, -1);
    for (int a = 1; a < len; ++a) {
      seg[a] = V++;
    }
    for (int j = 0; j < len; ++j) {
      seg[len + j] = (us[j] < N) ? us[j] : -1;
    }
  }
  void ae(Scc &scc) const {
    for (int a = 2; a < len << 1; ++a) {
      if (~seg[a >> 1] && ~seg[a]) {
        scc.ae(seg[a >> 1], seg[a]);
      }
    }
  }
  void query(Scc &scc, int u0, int u1, int src) const {
    int a = lower_bound(us.begin(), us.end(), u0) - us.begin();
    int b = lower_bound(us.begin(), us.end(), u1) - us.begin();
    if (a < b) {
// cerr<<"  query "<<u0<<" "<<u1<<" "<<src<<"; "<<a<<" "<<b<<endl;
// cerr<<"    us = ";pv(us.begin(),us.end());
      for (a += len, b += len; a < b; a >>= 1, b >>= 1) {
        if (a & 1) scc.ae(src, seg[a++]);
        if (b & 1) scc.ae(src, seg[--b]);
      }
    }
  };
};
int segN;
vector<Seg> segC, segD;

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    C.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &C[u]); --C[u]; }
    D.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &D[u]); --D[u]; }
    A.resize(M);
    B.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    banCD.assign(N, {});
    banDC.assign(N, {});
    for (int i = 0; i < M; ++i) {
      banCD[A[i]].push_back(B[i]);
      banDC[B[i]].push_back(A[i]);
    }
    
    vector<pair<int, int>> cs(N), ds(N);
    for (int u = 0; u < N; ++u) {
      cs[u] = make_pair(C[u], u);
      ds[u] = make_pair(D[u], u);
    }
    sort(cs.begin(), cs.end());
    sort(ds.begin(), ds.end());
    vector<int> posC(N, -1), posD(N, -1);
    for (int j = 0; j < N; ++j) {
      posC[cs[j].second] = j;
      posD[ds[j].second] = j;
    }
    
    for (segN = 1; segN < N; segN <<= 1) {}
    segC.assign(segN << 1, {});
    segD.assign(segN << 1, {});
    for (int j = 0; j < N; ++j) {
      segC[segN + j].us.push_back(cs[j].second);
      segD[segN + j].us.push_back(ds[j].second);
    }
    for (int j = N; j < segN; ++j) {
      segC[segN + j].us.push_back(j);
      segD[segN + j].us.push_back(j);
    }
    for (int a = segN; --a; ) {
      segC[a].us = merge(segC[a << 1].us, segC[a << 1 | 1].us);
      segD[a].us = merge(segD[a << 1].us, segD[a << 1 | 1].us);
    }
    
    V = N;
    for (int a = 1; a < segN << 1; ++a) segC[a].build();
    for (int a = 1; a < segN << 1; ++a) segD[a].build();
    Scc scc(V);
    for (int a = 1; a < segN << 1; ++a) segC[a].ae(scc);
    for (int a = 1; a < segN << 1; ++a) segD[a].ae(scc);
    
    // x -> y, x < y, C[x] < D[y]
    for (int x = 0; x < N; ++x) {
      vector<int> js;
      js.push_back(lower_bound(ds.begin(), ds.end(), make_pair(C[x], -1)) - ds.begin() - 1);
      js.push_back(N);
      for (const int y : banCD[x]) if (C[x] < D[y]) {
        js.push_back(posD[y]);
      }
      sort(js.begin(), js.end());
      const int jsLen = js.size();
      for (int k = 0; k < jsLen - 1; ++k) {
        int a = js[k] + 1, b = js[k + 1];
        if (a < b) {
// cerr<<"CD "<<x<<" "<<a<<" "<<b<<endl;
          for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
            if (a & 1) segD[a++].query(scc, x + 1, N, x);
            if (b & 1) segD[--b].query(scc, x + 1, N, x);
          }
        }
      }
    }
    // y -> x, x < y, C[x] > D[y]
    for (int y = 0; y < N; ++y) {
      vector<int> js;
      js.push_back(lower_bound(cs.begin(), cs.end(), make_pair(D[y], -1)) - cs.begin() - 1);
      js.push_back(N);
      for (const int x : banDC[y]) if (C[x] > D[y]) {
        js.push_back(posC[x]);
      }
      sort(js.begin(), js.end());
      const int jsLen = js.size();
      for (int k = 0; k < jsLen - 1; ++k) if (js[k] + 1 < js[k + 1]) {
        int a = js[k] + 1, b = js[k + 1];
        if (a < b) {
// cerr<<"DC "<<y<<" "<<a<<" "<<b<<endl;
          for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
            if (a & 1) segC[a++].query(scc, 0, y, y);
            if (b & 1) segC[--b].query(scc, 0, y, y);
          }
        }
      }
    }
    
    scc.run();
    const auto uss = scc.group();
// cerr<<"ids = ";pv(scc.ids.begin(),scc.ids.end());
// for(auto us:uss){cerr<<"  us = ";pv(us.begin(),us.end());}
// for(auto us:uss)if(us[0]<N){cerr<<"  us = ";pv(us.begin(),us.end());}
    
    set<pair<int, int>> ans;
    for (int z = 0; z < scc.l; ++z) {
      vector<int> vs;
      for (const int u : uss[z]) if (u < N) {
        vs.push_back(u);
      }
      const int vsLen = vs.size();
      if (vsLen >= 2) {
        for (int h = 0; h < vsLen - 1; ++h) {
          ans.emplace(vs[h], vs[h + 1]);
        }
        ans.emplace(vs[vsLen - 1], vs[0]);
      }
    }
    
    vector<unordered_set<int>> graph(scc.l);
    for (int i = 0; i < (int)scc.as.size(); ++i) {
      const int z = scc[scc.as[i]];
      const int w = scc[scc.bs[i]];
      if (z != w) {
        graph[z].insert(w);
      }
    }
    vector<unordered_set<int>> dp(scc.l);
    for (int z = scc.l; --z >= 0; ) {
      for (const int w : graph[z]) {
        for (const int v : dp[w]) {
          dp[z].insert(v);
        }
      }
      const int u = uss[z][0];
      if (u < N) {
        for (const int v : dp[z]) {
          ans.emplace(u, v);
        }
        dp[z].clear();
        dp[z].insert(u);
      }
    }
    
    printf("%d\n", (int)ans.size());
    for (const auto &edge : ans) {
      printf("%d %d\n", edge.first + 1, edge.second + 1);
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード