結果
問題 |
No.2900 Star Divine
|
ユーザー |
|
提出日時 | 2024-09-22 10:05:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,634 bytes |
コンパイル時間 | 2,191 ms |
コンパイル使用メモリ | 203,564 KB |
最終ジャッジ日時 | 2025-02-24 11:31:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; int main() { cin.tie(0); ios::sync_with_stdio(0); int q; cin >> q; while (q--) { int x, y, m; cin >> x >> y >> m; vector<vector<int>> g(x), v(y); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; a -= 1, b -= 1; g[a].push_back(b); } for (int i = 0; i < x; ++i) { sort(g[i].begin(), g[i].end()); g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end()); for (int j : g[i]) { v[j].push_back(i); } } vector<int> r1, r2; vector<int> deg(x); for (int i = 0; i < y; ++i) { vector<int> h1, h2; for (int j : v[i]) { if (g[j].back() == i) { if (deg[j] % 2 == 0) h1.push_back(j); else h2.push_back(j); } } if (h1.size() + 1 >= h2.size()) { r2.push_back(i); for (int j : v[i]) { deg[j] += 1; } for (int j : h1) { r1.push_back(j); } } else { for (int j : h2) { r1.push_back(j); } } } cout << r1.size() << " " << r2.size() << "\n"; for (int i : r1) { cout << i + 1 << " "; } cout << "\n"; for (int i : r2) { cout << i + 1 << " "; } cout << "\n"; } }