結果

問題 No.2072 Anatomy
ユーザー 👑 NachiaNachia
提出日時 2022-09-16 22:42:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 2,776 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 87,804 KB
実行使用メモリ 11,056 KB
最終ジャッジ日時 2023-08-23 16:16:37
合計ジャッジ時間 3,457 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 46 ms
9,636 KB
testcase_09 AC 46 ms
10,632 KB
testcase_10 AC 44 ms
9,448 KB
testcase_11 AC 47 ms
10,176 KB
testcase_12 AC 35 ms
8,384 KB
testcase_13 AC 50 ms
10,708 KB
testcase_14 AC 31 ms
7,956 KB
testcase_15 AC 29 ms
7,768 KB
testcase_16 AC 49 ms
10,624 KB
testcase_17 AC 47 ms
10,864 KB
testcase_18 AC 24 ms
6,936 KB
testcase_19 AC 51 ms
10,976 KB
testcase_20 AC 50 ms
10,900 KB
testcase_21 AC 48 ms
11,056 KB
testcase_22 AC 51 ms
10,892 KB
testcase_23 AC 47 ms
10,884 KB
testcase_24 AC 46 ms
11,040 KB
testcase_25 AC 51 ms
10,888 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 49 ms
10,976 KB
testcase_28 AC 44 ms
10,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"


#include <vector>
#include <algorithm>
#line 2 "nachia\\set\\dsu.hpp"

#line 5 "nachia\\set\\dsu.hpp"


namespace nachia {
    struct Dsu{
    private:
        std::vector<int> w;
    public:
        Dsu(int n) : w(n, -1) {}
        int leader(int u){
            if(w[u] < 0) return u;
            return w[u] = leader(w[u]);
        }
        int merge(int u, int v){
            u = leader(u);
            v = leader(v);
            if(u == v) return u;
            if(-w[u] < -w[v]) std::swap(u, v);
            else if(w[u] == w[v]) w[u]--;
            w[v] = u;
            return u;
        }
        bool same(int u, int v){
            return leader(u) == leader(v);
        }
    };
} // namespace nachia
#line 6 "Main.cpp"

namespace nachia{

struct MergerTree{
    std::vector<int> parent;
    std::vector<int> weight;
    int node_count = 0;

    MergerTree(int n, std::vector<std::pair<int,int>> edges){
        Dsu dsu(n);
        std::vector<int> root(n);
        for(int i=0; i<n; i++) root[i] = i;
        node_count = n;
        parent.assign(n+edges.size(), -1);
        weight.assign(n+edges.size(), -1);
        for(size_t i=0; i<edges.size(); i++){
            int u = edges[i].first;
            int v = edges[i].second;
            u = dsu.leader(u);
            v = dsu.leader(v);
            if(u == v){
                parent[root[u]] = node_count;
                root[u] = node_count++;
                weight[root[u]] = (int)i;
                continue;
            }
            parent[root[u]] = node_count;
            parent[root[v]] = node_count;
            int r = dsu.merge(u, v);
            root[r] = node_count++;
            weight[root[r]] = (int)i;
        }
    }

    std::vector<int> getAllDepth() const {
        std::vector<int> res(node_count, 0);
        for(int i=node_count-1; i>=0; i--) if(parent[i] != -1) res[i] = res[parent[i]] + 1;
        return res;
    }
};

} // namespace nachia


#include <iostream>
#include <string>
#line 54 "Main.cpp"
#include <queue>
#include <atcoder/modint>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using Modint = atcoder::static_modint<998244353>;


int main(){
    int N, M; cin >> N >> M;
    vector<pair<int,int>> E(M);
    rep(i,M){
        int u,v; cin >> u >> v; u--; v--;
        E[i] = {u,v};
    }
    reverse(E.begin(), E.end());
    nachia::MergerTree mt(N, E);
    auto d = mt.getAllDepth();
    int ans = *max_element(d.begin(), d.end());
    cout << ans << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0