結果

問題 No.2900 Star Divine
コンテスト
ユーザー 獅子座じゃない人
提出日時 2024-08-24 14:12:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,262 bytes
コンパイル時間 1,276 ms
コンパイル使用メモリ 107,388 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-20 00:28:07
合計ジャッジ時間 2,858 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void solve() {
    int x,y,m;
    cin >> x >> y >> m;
    vector<pair<int, int>> uv(m);
    for(int i=0;i<m;++i){
        cin >> uv[i].first >> uv[i].second;
        --uv[i].first; --uv[i].second;
    }
    sort(uv.begin(), uv.end());
    uv.erase(unique(uv.begin(), uv.end()), uv.end());
    if(x<=y){
        cout << 0 << " " << y << endl << endl;
        for(int i=0;i<y;++i){
            cout << i+1 << " ";
        }
        cout << endl;
        return;
    }
    int m_=uv.size();
    vector<int> u(m_);
    vector<int> v(m_);
    vector<int> b_deg(x);
    vector<int> r_deg(y);
    for(int i=0;i<m_;++i){
        u[i]=uv[i].first;
        v[i]=uv[i].second;
        ++b_deg[u[i]];
        ++r_deg[v[i]];
    }
    int odd_stars=0;
    for(int i=0;i<x;++i){
        if(b_deg[i]%2>0){
            ++odd_stars;
        }
    }
    if((odd_stars+y)*2>=x+y){
        cout << odd_stars << " " << y << endl;
        for(int i=0;i<x;++i){
            if(b_deg[i]%2>0){
                cout << i+1 << " ";
            }
        }
        cout << endl;
        for(int i=0;i<y;++i){
            cout << i+1 << " ";
        }
        cout << endl;
        return;
    }
    vector<int> adj_even_stars(y);
    for(int i=0;i<m_;++i){
        if(b_deg[u[i]]%2==0){
            ++adj_even_stars[v[i]];
        }
    }
    int removed_star=0;
    for(int i=1;i<y;++i){
        if(adj_even_stars[i]*2-r_deg[i]>adj_even_stars[removed_star]*2-r_deg[removed_star]){
            removed_star=i;
        }
    }
    for(int i=0;i<m_;++i){
        if(v[i]==removed_star){
            if(b_deg[u[i]]%2>0){
                --odd_stars;
            } else {
                ++odd_stars;
            }
            --b_deg[u[i]];
        }
    }
    cout << odd_stars << " " << y-1 << endl;
    for(int i=0;i<x;++i){
        if(b_deg[i]%2>0){
            cout << i+1 << " ";
        }
    }
    cout << endl;
    for(int i=0;i<y;++i){
        if(i!=removed_star){
            cout << i+1 << " ";
        }
    }
    cout << endl;
}

int main(void) {
    int t;
    cin >> t;
    while(t--){
        solve();
        if(t>0){
            cout << endl;
        }
    }
    return 0;
}
0