結果

問題 No.2677 Minmax Independent Set
ユーザー hirakuuuuhirakuuuu
提出日時 2024-03-15 22:59:18
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,412 bytes
コンパイル時間 3,334 ms
コンパイル使用メモリ 260,476 KB
実行使用メモリ 54,180 KB
最終ジャッジ日時 2024-03-15 22:59:31
合計ジャッジ時間 11,450 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 182 ms
17,956 KB
testcase_06 AC 181 ms
18,468 KB
testcase_07 AC 189 ms
18,852 KB
testcase_08 AC 208 ms
19,876 KB
testcase_09 AC 180 ms
21,796 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 185 ms
54,180 KB
testcase_13 AC 176 ms
28,068 KB
testcase_14 AC 189 ms
28,068 KB
testcase_15 AC 193 ms
36,388 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 133 ms
15,108 KB
testcase_29 AC 214 ms
39,200 KB
testcase_30 AC 2 ms
6,676 KB
testcase_31 AC 2 ms
6,676 KB
testcase_32 AC 2 ms
6,676 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 AC 56 ms
7,808 KB
testcase_51 AC 6 ms
6,676 KB
testcase_52 AC 123 ms
13,068 KB
testcase_53 AC 116 ms
12,340 KB
testcase_54 AC 5 ms
6,676 KB
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 AC 142 ms
15,108 KB
testcase_61 WA -
testcase_62 AC 148 ms
22,180 KB
testcase_63 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define rrep(i, a, n) for(int i = a; i >= n; i--)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1LL<<60;

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template <class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
class RerootingDP
{
    int n, root, inner_edge_id;
    vector<E> outs;
    struct edge {
        int to, idx, xdi;
    };
    vector<edge> es;
    vector<int> start;

    int outs_start(int v){
        int res = start[v]-v;
        if(root < v) res++;
        return res;
    }

    void es_build(){
        vector<edge> nes(2*n-2);
        vector<int> nstart(n+2, 0);
        for(int i = 0; i < 2*n-2; i++){
            nstart[start[i]+2]++;
        }
        for(int i = 0; i < n; i++){
            nstart[i+1] += nstart[i];
        }
        for(int i = 0; i < 2*n-2; i++){
            nes[nstart[start[i]+1]++] = es[i];
        }
        swap(es, nes);
        swap(start, nstart);
    }
    
public:
    RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) {
        es.resize(2*n-2);
        start.resize(2*n-2);
        if(n == 1) es_build();
    }

    void add_edge(int u, int v, int idx, int xdi){ // u→v, v→uの有向辺をそれぞれ追加
        start[inner_edge_id] = u;
        es[inner_edge_id] = {v, idx, xdi};
        inner_edge_id++;
        start[inner_edge_id] = v;
        es[inner_edge_id] = {u, xdi, idx};
        inner_edge_id++;
        if(inner_edge_id == 2*n-2){
            es_build();
        }
    }

    vector<V> build(int root_ = 0){
        root = root_;
        vector<V> subdp(n); subdp[0] = put_vertex(e(), 0);
        outs.resize(n);
        vector<int> geta(n+1, 0);
        for(int i = 0; i < n; i++){
            geta[i+1] = start[i+1]-start[i]-1;
        }
        geta[root+1]++;
        for(int i = 0; i < n; i++){
            geta[i+1] += geta[i];
        }

        auto dfs = [&](auto sfs, int v, int f)-> void {
            E val = e();
            for(int i = start[v]; i < start[v+1]; i++){
                if(es[i].to == f){
                    swap(es[start[v+1]-1], es[i]);
                }
                if(es[i].to == f) continue;
                sfs(sfs, es[i].to, v);
                E nval = put_edge(subdp[es[i].to], es[i].idx);
                outs[geta[v]++] = nval;
                val = merge(val, nval);
            }
            subdp[v] = put_vertex(val, v);
        };
        dfs(dfs, root, -1);
        return subdp;
    }

    vector<V> reroot(){
        vector<E> reverse_edge(n);
        reverse_edge[root] = e();
        vector<V> answers(n);
        auto dfs = [&](auto sfs, int v) -> void {
            int le = outs_start(v);
            int ri = outs_start(v+1);
            int siz = ri-le;
            vector<E> rui(siz+1);
            rui[siz] = e();
            for(int i = siz-1; i >= 0; i--){
                rui[i] = merge(outs[le+i], rui[i+1]);
            }
            answers[v] = put_vertex(merge(rui[0], reverse_edge[v]), v);
            E lui = e();
            for(int i = 0; i < siz; i++){
                V rdp = put_vertex(merge(merge(lui, rui[i+1]), reverse_edge[v]), v);
                reverse_edge[es[start[v]+i].to] = put_edge(rdp, es[start[v]+i].xdi);
                lui = merge(lui, outs[le+i]);
                sfs(sfs, es[start[v]+i].to);
            }
        };
        dfs(dfs, root);
        return answers;
    }
};

using E = pair<int, int>;
using V = pair<int, int>;
ll m;
E merge(E a, E b){
    return {a.first+b.first, a.second+b.second};
}
E e(){
    return E({0, 0});
}
E put_edge(V v, int i){
    return {v.second+1, v.first};
}
V put_vertex(E e, int v){
    return e;
}


int main(){
    int n; cin >> n;
    RerootingDP<E, V, merge, e, put_edge, put_vertex> g(n);
    rep(i, 0, n-1){
        int u, v; cin >> u >> v;
        u--, v--;
        g.add_edge(u, v, i, i);
    }
    g.build();
    vector<V> score = g.reroot();
    int ans = IINF;
    rep(i, 0, n){
        // cout << score[i].first << ' ' << score[i].second << endl;
        chmin(ans, score[i].second+1);
    }
    cout << ans << endl;
    
    return 0;
}
0