結果

問題 No.2301 Namorientation
ユーザー asaringoasaringo
提出日時 2023-05-12 22:47:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,341 bytes
コンパイル時間 3,322 ms
コンパイル使用メモリ 231,092 KB
実行使用メモリ 87,208 KB
最終ジャッジ日時 2024-05-06 12:50:03
合計ジャッジ時間 19,111 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,192 KB
testcase_01 AC 5 ms
8,192 KB
testcase_02 AC 5 ms
8,192 KB
testcase_03 AC 5 ms
8,320 KB
testcase_04 AC 5 ms
8,320 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 5 ms
8,192 KB
testcase_08 AC 4 ms
8,192 KB
testcase_09 AC 5 ms
8,192 KB
testcase_10 AC 5 ms
8,192 KB
testcase_11 AC 4 ms
8,192 KB
testcase_12 AC 300 ms
43,364 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 247 ms
87,208 KB
testcase_23 AC 240 ms
85,880 KB
testcase_24 AC 205 ms
73,272 KB
testcase_25 AC 164 ms
53,664 KB
testcase_26 AC 206 ms
67,368 KB
testcase_27 AC 540 ms
66,928 KB
testcase_28 AC 532 ms
66,792 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std ;
#define fast_input_output ios::sync_with_stdio(false); cin.tie(nullptr);
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll ;
typedef long double ld ;
typedef pair<ll,ll> P ;
typedef tuple<ll,ll,ll> TP ;
#define chmin(a,b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
#define bit_count(x) __builtin_popcountll(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl
#define DEBUG(...) ; cout << #__VA_ARGS__ << endl ; for(auto x : {__VA_ARGS__}) cout << x << "  " ; cout << endl ;
#define DEBUG_LIST(...) cout << #__VA_ARGS__ << endl ; DEBUG_REP(__VA_ARGS__) ;
#define DEBUG_REP(V) cout << "{ " ; repi(itr,V) cout << *itr << ", " ; cout << "}" << endl ;
#define debug(a) cout << #a << " " << a << endl
#define all(a) a.begin(), a.end()
#define endl "\n"

struct edge{
    int from;
    int to;
    int id;
};

template<typename Edge = edge> struct DfsTree{
    private:
        int n;
        vector<int> ord;
        vector<int> low;
        vector<vector<Edge>> G;
        vector<vector<Edge>> back_edge; // 後退辺
        vector<int> topological_sort;
        vector<Edge> bridge; // 橋
        vector<int> aps; // 関節点
        vector<vector<int>> tecc; // 連結成分iが含んでいるノードリスト
        vector<int> tecc_idx; // ノードの連結成分番号
        vector<vector<int>> tecc_tree; // 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト

        void init_(int n_){
            n = n_;
            ord.resize(n,-1);
            low.resize(n,n);
            G.resize(n);
            back_edge.resize(n);
            tecc_idx.resize(n,-1);
        }

        // 有向辺を張る
        void add_edge_(int u, Edge v){
            G[u].push_back(v);
        }

        void build_(){
            low_link();
            two_edge_connected_component();
        }

        void low_link(){
            int current = 0;
            for(int i = 0; i < n; i++) if(ord[i] == -1) dfs_bridge(0,-1,current);
        }

        void dfs_bridge(int v, int prev, int &current){
            bool is_root = prev == -1 ? true : false;
            bool is_aps = false;
            ord[v] = current++;
            int count = 0;
            topological_sort.push_back(v);
            for(Edge e : G[v]){
                auto[from, u, id] = e;
                if(u == prev) continue;
                if(ord[u] != -1) {
                    count++;
                    low[v] = min(low[v],ord[u]);
                    back_edge[v].push_back(e);
                    continue;
                }
                dfs_bridge(u,v,current);
                low[v] = min(low[v], low[u]);
                if(!is_root && ord[v] <= low[u]) is_aps = true;
                if(ord[v] < low[u]) bridge.emplace_back(e);
            }
            if(is_root && count >= 2) is_aps = true;
            if(is_aps) aps.push_back(v);
        }

        void two_edge_connected_component(){
            int id = 0;
            int bridge_size = (int)bridge.size();
            tecc_tree.resize(bridge_size+1);
            for(int i = 0; i < n; i++) {
                if(tecc_idx[i] != -1) continue;
                tecc.push_back({});
                dfs(i,-1,(int)tecc.size()-1);
            }
        }

        void dfs(int v, int prev, int id){
            tecc_idx[v] = id;
            tecc[id].push_back(v);
            for(edge e : G[v]){
                int u = e.to;
                if(u == prev) continue;
                // すでに訪れているか
                if(tecc_idx[u] != -1) continue;
                // 橋であるか
                if(low[u] > ord[v] || low[v] > ord[u]) {
                    tecc.push_back({});
                    dfs(u,v,(int)tecc.size()-1);
                    tecc_tree[id].push_back(tecc_idx[u]);
                    tecc_tree[tecc_idx[u]].push_back(id);
                }
                else dfs(u,v,id);
            }
        }

    public:
        DfsTree(){}
        DfsTree(int n) { init_(n); }
        void init(int n) { init_(n); }
        void add_edge(int u, Edge v){ add_edge_(u, v); }
        void build() { build_(); }
        vector<Edge> get_bridge() { return bridge; } // 橋を取得
        vector<int> get_aps() { return aps; } // 関節点を取得
        vector<vector<int>> get_graph() { return G; } // グラフの取得
        vector<vector<Edge>> get_back_edge() { return back_edge; } // 後退辺の取得
        vector<vector<int>> get_all_two_edge_connected_compoonent() { return tecc; }
        vector<int> get_two_edge_connected_compoonent(int k) { return tecc[k]; } // 集約したグラフのノードkに含まれている元々の頂点集合
        int root(int v) { return tecc_idx[v]; } // 元々のノードが集約されたあとどのノードになったか
        vector<vector<int>> get_tecc_tree() { return tecc_tree; } // 元々のグラフを集約して得られた新しいグラフ
};

int n, m;
bool B[202020];

struct E{
    int to;
    int id;
};

vector<E> G[202020];
pair<int,int> res[202020];
pair<int,int> tmp[202020];
bool used[202020];

int node;

void dfs(int v, int prev, int id){
    used[v] = true;
    if(id != -1){
        if(!B[id]) res[id] = {prev,v};
        else res[id] = {v,prev};
    }
    for(E e : G[v]){
        int u = e.to;
        if(u == prev) continue;
        if(used[u] && node != u) continue;
        dfs(u,v,e.id);
    }
}

int main(){
    cin >> n;
    DfsTree tree;
    tree.init(n);
    rep(i,n){
        int u , v ;
        cin >> u >> v ;
        u-- ; v-- ;
        tree.add_edge(u,{u,v,i});
        tree.add_edge(v,{v,u,i});
        G[u].push_back({v,i});
        G[v].push_back({u,i});
        tmp[i] = {u,v};
    }
    rep(i,n) if(G[i].size() > 2) node = i;
    tree.build();
    auto bridge = tree.get_bridge();
    for(auto e : bridge){
        B[e.id] = true;
    }
    dfs(node,-1,-1);
    rep(i,n){
        if(res[i] == tmp[i]) cout << "->" << endl;
        else cout << "<-" << endl;
    }
}
0