結果
問題 | No.1914 Directed by Two Sequences |
ユーザー | HYEA LEE |
提出日時 | 2022-01-24 01:20:09 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,834 bytes |
コンパイル時間 | 5,523 ms |
コンパイル使用メモリ | 295,776 KB |
実行使用メモリ | 327,208 KB |
最終ジャッジ日時 | 2024-12-16 01:31:25 |
合計ジャッジ時間 | 103,259 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 KB |
testcase_01 | AC | 2 ms
325,180 KB |
testcase_02 | AC | 63 ms
12,548 KB |
testcase_03 | AC | 68 ms
14,800 KB |
testcase_04 | AC | 70 ms
12,944 KB |
testcase_05 | AC | 65 ms
326,444 KB |
testcase_06 | AC | 65 ms
12,716 KB |
testcase_07 | AC | 62 ms
326,780 KB |
testcase_08 | AC | 63 ms
12,620 KB |
testcase_09 | AC | 63 ms
327,208 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | AC | 586 ms
59,264 KB |
testcase_20 | AC | 620 ms
59,332 KB |
testcase_21 | AC | 623 ms
60,012 KB |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | AC | 494 ms
320,640 KB |
testcase_33 | AC | 84 ms
8,380 KB |
testcase_34 | TLE | - |
testcase_35 | AC | 115 ms
8,776 KB |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2,bmi2,lzcnt,fma") #include<bits/stdc++.h> using namespace std; vector<pair<int, int>> solve(vector<int> A, vector<int> B, vector<pair<int, int>> E) { int N = A.size(); vector<vector<int>> conn(N); vector<vector<bool>> adj(N, vector<bool>(N)); for(auto& [u, v]: E) { if(u > v) swap(u, v); conn[u].push_back(v), conn[v].push_back(u); adj[v][u] = adj[u][v] = 1; } sort(E.begin(), E.end()); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; vector<int> deg(N), color(N, -1); for(int i=0; i<N; ++i) deg[i] = conn[i].size(), Q.emplace(deg[i], i); while(!Q.empty()) { int u = Q.top().second; Q.pop(); if(color[u] != -1) continue; vector<bool> exist(conn[u].size()+1); for(int v: conn[u]) { Q.emplace(deg[v]--, v); if(color[v] != -1 && color[v] < (int)exist.size()) exist[color[v]] = 1; } for(int i=0; i<(int)exist.size(); ++i) if(!exist[i]) { color[u] = i; break; } assert(color[u] != -1); } int K = 1+*max_element(color.begin(), color.end()); vector<vector<int>> cliques(K); for(int i=0; i<N; ++i) cliques[color[i]].push_back(i); auto cmp = [&](int x, int y) { if(x == y) return false; if(x < y) return A[x] < B[y]; return B[x] < A[y]; }; function<void(vector<int>::iterator, vector<int>::iterator)> hamiltonian = [&](vector<int>::iterator st, vector<int>::iterator ed) { int N = distance(st, ed); if(N == 1) return; auto mi = st + N / 2; hamiltonian(st, mi); hamiltonian(mi, ed); vector<int> buffer; buffer.reserve(N); auto l = st, r = mi; while(l != mi || r != ed) { if(l == mi) buffer.push_back(*r++); else if(r == ed) buffer.push_back(*l++); else if(cmp(*l, *r)) buffer.push_back(*l++); else buffer.push_back(*r++); } copy(buffer.begin(), buffer.end(), st); return; }; auto exist = [&](int u, int v) { return cmp(u, v) && !adj[u][v]; }; vector<pair<int, int>> ans; for(int i=0; i<K; ++i) { hamiltonian(cliques[i].begin(), cliques[i].end()); for(int j=0; j<(int)cliques[i].size()-1; ++j) ans.emplace_back(cliques[i][j], cliques[i][j+1]); } for(int i=0; i<K; ++i) for(int j=i; j<K; ++j) { for(int u: cliques[j]) { for(int k=0; k<(int)cliques[i].size(); ++k) { int v = cliques[i][k]; if(exist(u, v)) { ans.emplace_back(u, v); break; } } if(i != j) for(int k=(int)cliques[i].size()-1; k>=0; --k) { int v = cliques[i][k]; if(exist(v, u)) { ans.emplace_back(v, u); break; } } } } sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<int> A(N), B(N); for(int&x: A) cin >> x; for(int&x: B) cin >> x; vector<pair<int, int>> E(M); for(auto& [u, v]: E) { cin >> u >> v; --u; --v; } auto ret = solve(A, B, E); cout << ret.size() << '\n'; for(auto [a, b]: ret) cout << a+1 << " " << b+1 << '\n'; }