結果
| 問題 |
No.1914 Directed by Two Sequences
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2022-04-22 23:27:20 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 MLE * 3 -- * 27 |
ソースコード
#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;
}