結果
問題 | No.2678 Minmax Independent Set (Hack) |
ユーザー | NokonoKotlin |
提出日時 | 2024-03-13 21:06:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,155 bytes |
コンパイル時間 | 2,685 ms |
コンパイル使用メモリ | 255,820 KB |
実行使用メモリ | 15,116 KB |
最終ジャッジ日時 | 2024-09-29 23:06:42 |
合計ジャッジ時間 | 3,373 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ソースコード
#include <bits/stdc++.h> using namespace std; // 次数 4 の頂点が一部最適解 (確率が足りない) int main(int argc, char* argv[]) { int N = 199995; int L = 39999; // 列の個数 vector<vector<int>> G(N + 1); for (int i = 1; i < L; i++) { G[i].push_back(i + 1); G[i + 1].push_back(i); } int id = L + 1; for (int u = 1; u <= L; u++) { int now = u; G[now].push_back(id); G[id].push_back(now); now = id; id++; G[now].push_back(id); G[id].push_back(now); id++; now = u; G[now].push_back(id); G[id].push_back(now); now = id; id++; G[now].push_back(id); G[id].push_back(now); id++; } stack<int> S; S.push(1); vector<int> visited(N + 1, 0); cout << N << endl; while (!S.empty()) { int now = S.top(); S.pop(); visited[now] = 1; for (int nx : G[now]) { if (visited[nx]) continue; cout << min(now, nx) << " " << max(nx, now) << "\n"; S.push(nx); } } return 0; }