結果

問題 No.2301 Namorientation
ユーザー shobonvip
提出日時 2023-05-12 21:55:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 520 ms / 3,000 ms
コード長 1,841 bytes
コンパイル時間 4,233 ms
コンパイル使用メモリ 257,428 KB
最終ジャッジ日時 2025-02-12 22:38:43
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef modint998244353 mint;
typedef long long ll;
int main(){
    int n; cin >> n;
    vector<vector<pair<int,int>>> ikeru;
    ikeru.resize(n);
    vector<int> deg(n);
    vector<int> x(n), y(n);
    for (int i=0; i<n; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        deg[a]++;
        deg[b]++;
        x[i] = a;
        y[i] = b;
        ikeru[a].push_back(pair(b,i));
        ikeru[b].push_back(pair(a,i));
    }
    vector<int> mada;
    vector<bool> isnamori(n, true);
    vector<int> comefrom(n,-1);
    vector<int> kousha(n,-1);
    for (int i=0; i<n; i++){
        if (deg[i] == 1){
            mada.push_back(i);
        }
    }
    while (!mada.empty()){
        int i = mada.back();
        mada.pop_back();
        isnamori[i] = false;
        for (auto [j,c]: ikeru[i]){
            deg[j]--;
            if (deg[j] == 1){
                mada.push_back(j);
            }else if (deg[j] <= 0){
                kousha[c] = i;
            }
        }
    }
    vector<bool> tansaku(n);
    for (int i=0; i<n; i++){
        if (!isnamori[i]){
            tansaku[i] = true;
        }
    }
    for (int i=0; i<n; i++){
        if (isnamori[i]){
            mada.push_back(i);
            break;
        }
    }
    vector<int> arr;
    while(!mada.empty()){
        int i = mada.back();
        mada.pop_back();
        if (tansaku[i]) continue;
        arr.push_back(i);
        tansaku[i] = true;
        for (auto [j,c]: ikeru[i]){
            if (!tansaku[j]){
                mada.push_back(j);
            }
        }
    }
    int m = arr.size();
    arr.push_back(arr[0]);
    
    for (int i=0; i<m; i++){
        comefrom[arr[i+1]] = arr[i];
    }
    for (int i=0; i<n; i++){
        if (isnamori[x[i]] && isnamori[y[i]]){
            if (comefrom[y[i]] == x[i]){
                cout << "->" << endl;
            }else{
                cout << "<-" << endl;
            }
        }else if (isnamori[x[i]] && !isnamori[y[i]]){
            cout << "<-" << endl;
        }else if (!isnamori[x[i]] && isnamori[y[i]]){
            cout << "->" << endl;
        }else{
            if (kousha[i] == y[i]){
                cout << "->" << endl;
            }else{
                cout << "<-" << endl;
            }
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0