結果

問題 No.2301 Namorientation
ユーザー asaringoasaringo
提出日時 2023-05-13 02:47:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 367 ms / 3,000 ms
コード長 6,345 bytes
コンパイル時間 2,617 ms
コンパイル使用メモリ 221,032 KB
実行使用メモリ 51,992 KB
最終ジャッジ日時 2024-05-06 15:15:44
合計ジャッジ時間 14,952 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,192 KB
testcase_01 AC 5 ms
8,320 KB
testcase_02 AC 5 ms
8,192 KB
testcase_03 AC 5 ms
8,320 KB
testcase_04 AC 5 ms
8,192 KB
testcase_05 AC 4 ms
8,192 KB
testcase_06 AC 5 ms
8,320 KB
testcase_07 AC 4 ms
8,192 KB
testcase_08 AC 4 ms
8,192 KB
testcase_09 AC 4 ms
8,192 KB
testcase_10 AC 5 ms
8,064 KB
testcase_11 AC 4 ms
8,064 KB
testcase_12 AC 187 ms
30,512 KB
testcase_13 AC 167 ms
28,308 KB
testcase_14 AC 358 ms
45,184 KB
testcase_15 AC 220 ms
32,928 KB
testcase_16 AC 292 ms
39,964 KB
testcase_17 AC 193 ms
31,472 KB
testcase_18 AC 296 ms
40,604 KB
testcase_19 AC 145 ms
27,148 KB
testcase_20 AC 294 ms
40,280 KB
testcase_21 AC 205 ms
32,684 KB
testcase_22 AC 192 ms
51,992 KB
testcase_23 AC 192 ms
51,420 KB
testcase_24 AC 161 ms
44,332 KB
testcase_25 AC 131 ms
37,888 KB
testcase_26 AC 154 ms
45,768 KB
testcase_27 AC 354 ms
45,220 KB
testcase_28 AC 358 ms
45,288 KB
testcase_29 AC 363 ms
45,400 KB
testcase_30 AC 354 ms
45,232 KB
testcase_31 AC 367 ms
45,312 KB
権限があれば一括ダウンロードができます

ソースコード

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};
    }
    tree.build();
    auto bridge = tree.get_bridge();
    for(auto e : bridge){
        B[e.id] = true;
    }
    rep(i,n) if(!B[i]) node = tmp[i].first;
    dfs(node,-1,-1);
    rep(i,n){
        if(res[i] == tmp[i]) cout << "->" << endl;
        else cout << "<-" << endl;
    }
}
0