結果
| 問題 | No.1914 Directed by Two Sequences |
| ユーザー |
 vjudge1
|
| 提出日時 | 2024-03-31 08:01:33 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 271 ms / 3,000 ms |
| コード長 | 6,177 bytes |
| コンパイル時間 | 7,522 ms |
| コンパイル使用メモリ | 282,080 KB |
| 実行使用メモリ | 18,564 KB |
| 最終ジャッジ日時 | 2024-09-30 17:50:43 |
| 合計ジャッジ時間 | 31,016 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 38 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>#include <unordered_map>#include <atcoder/all>using namespace std;using namespace atcoder;//using mint = modint998244353;#define rep(i,n) for (int i=0;i<n;i+=1)#define rrep(i,n) for (int i=n-1;i>-1;i--)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<endl;}ll lpow(int n,int k){ll res = 1;ll e = n;while (k){if (k&1){res *= e;}e = e * e;k >>= 1;}return res;}int op1(int i,int j){return min(i,j);}int e1(){return 1e5;}int op2(int i,int j){return max(i,j);}int e2(){return -1;}int A[100000];int B[100000];bool direct(int i,int j){if (i < j){return (A[i] < B[j]);}else{return (B[i] < A[j]);}}vec<int> hamilton_path(vec<int> V){int n = V.size();if (n <= 1){return V;}vec<int> VA = hamilton_path({V.begin(),V.begin()+(n/2)});vec<int> VB = hamilton_path({V.begin()+(n/2),V.begin()+(n)});vec<int> res = {};int i = 0;for (auto a:VA){while (i < VB.size() && direct(VB[i],a)){res.append(VB[i]);i++;}res.append(a);}for (int j=i;j<VB.size();j++){res.append(VB[j]);}return res;}vec<pii> solve(){int N,M;cin>>N>>M;for (int i=0;i<N;i++){cin>>A[i];A[i]--;}for (int i=0;i<N;i++){cin>>B[i];B[i]--;}vec<vec<int>> edge(N,vec<int>(0));int u,v;for (int i=0;i<M;i++){cin>>u>>v;edge[u-1].append(v-1);edge[v-1].append(u-1);}vec<pii> new_E = {};vec<int> group(N,0);for (int i=0;i<N;i++){int n = edge[i].size();vec<bool> mex(n+1,false);for (auto nv:edge[i]){if (nv < i && group[nv]<=n){mex[group[nv]] = true;}}for (int j=0;j<n+1;j++){if (!mex[j]){group[i] = j;break;}}}int n = *max_element(all(group)) + 1;vec<vec<int>> clique(n,vec<int>(0));rep(v,N){clique[group[v]].append(v);}vec<int> idx(N,-1);for (int i=0;i<n;i++){clique[i] = hamilton_path(clique[i]);for (int j=0;j<clique[i].size();j++){idx[clique[i][j]] = j;if (j!=clique[i].size()-1){new_E.append({clique[i][j],clique[i][j+1]});}}}vec<int> memo_to(N,1e5);vec<int> memo_from(N,-1);vec<int> ci(n);rep(i,n){ci[i]=n-1-i;};vec<int> idx_on_ci(n);rep(i,n){idx_on_ci[ci[i]]=i;};vec<vec<int>> ban(N,vec<int>(0));vec<int> Vs = {};segtree<int,op1,e1> seg_to_large(2*N);segtree<int,op1,e1> seg_to_small(2*N);segtree<int,op2,e2> seg_from_large(2*N);segtree<int,op2,e2> seg_from_small(2*N);rep(i,n){int target = ci[i];for (auto v:clique[target]){Vs.append(v);}sort(all(Vs));for (auto nv:clique[target]){for (auto v:edge[nv]){if (idx_on_ci[group[v]] <= i){ban[v].append(nv);}}}rrep(j,Vs.size()){v = Vs[j];for (auto nv:ban[v]){if (v < nv){seg_to_large.set(B[nv],1e5);}}chmin(memo_to[v],seg_to_large.prod(A[v],2*N));for (auto nv:ban[v]){if (v < nv){seg_to_large.set(B[nv],idx[nv]);}}if (group[v]==target){seg_to_large.set(B[v],idx[v]);}}rep(j,Vs.size()){v = Vs[j];for (auto nv:ban[v]){if (nv < v){seg_to_small.set(A[nv],1e5);}}chmin(memo_to[v],seg_to_small.prod(B[v],2*N));for (auto nv:ban[v]){if (nv < v){seg_to_small.set(A[nv],idx[nv]);}}if (group[v]==target){seg_to_small.set(A[v],idx[v]);}}rrep(j,Vs.size()){v = Vs[j];for (auto nv:ban[v]){if (v < nv){seg_from_large.set(B[nv],-1);}}chmax(memo_from[v],seg_from_large.prod(0,A[v]));for (auto nv:ban[v]){if (v < nv){seg_from_large.set(B[nv],idx[nv]);}}if (group[v]==target){seg_from_large.set(B[v],idx[v]);}}rep(j,Vs.size()){v = Vs[j];for (auto nv:ban[v]){if (nv < v){seg_from_small.set(A[nv],-1);}}chmax(memo_from[v],seg_from_small.prod(0,B[v]));for (auto nv:ban[v]){if (nv < v){seg_from_small.set(A[nv],idx[nv]);}}if (group[v]==target){seg_from_small.set(A[v],idx[v]);}}for (auto v:Vs){if (memo_to[v]!=1e5){int nv = clique[target][memo_to[v]];new_E.append({v,nv});memo_to[v] = 1e5;}if (memo_from[v]!=-1){int pv = clique[target][memo_from[v]];new_E.append({pv,v});memo_from[v] = -1;}ban[v] = {};if (group[v]==target){seg_to_large.set(B[v],1e5);seg_to_small.set(A[v],1e5);seg_from_large.set(B[v],-1);seg_from_small.set(A[v],-1) ;}}}sort(all(new_E));new_E.erase(unique(all(new_E)),new_E.end());return new_E;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);auto res = solve();cout<<res.size()<<endl;for (auto [u,v]:res){cout<<u+1<<" "<<v+1<<"\n";}}