#732781 (C++17) No.1817 Reversed Edges

提出ソース

結果

問題	No.1817 Reversed Edges
ユーザー	nrvft
提出日時	2022-01-21 21:58:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,519 bytes
コンパイル時間	3,629 ms
コンパイル使用メモリ	233,900 KB
実行使用メモリ	40,036 KB
最終ジャッジ日時	2023-08-17 05:55:29
合計ジャッジ時間	7,247 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 8,760 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	TLE	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T> void verr(const set<T> &st) { repa(a, st) cerr << a << " "; cerr << endl; }
template <class S, class T> void verr(const map<S, T> &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; }
template <class S, class T, class N> void verr(const vector<pair<S,T>>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; }
template <class T, class N> void verr(const vector<T>& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

template<
    class V,
    class E
>
struct ReRooting{
   private:
    struct edge{
        ll to;
        E val;
        ll rev; // G[to]におけるfromのindex
        edge(){}
        edge(ll t_, E v_, ll r_): to(t_), val(v_), rev(r_){}
    };
    ll N;
    vector<vector<edge>> G;         // グラフ
    vector<V> res;                  // 各頂点を根としたときの値
    vector<vector<V>> dp;
    vector<vector<int>> dpused;
    vector<int> resused;

    V vid;
    E eid;

  public:
    ReRooting(ll N_, V vid_, E eid_)
        : N(N_), G(N_), res(N_, vid_), resused(N_), dp(N_), dpused(N_), vid(vid_), eid(eid_) {}

    void add_edge(ll a, ll b, E c){
        G[a].emplace_back(b, c, G[b].size());
        G[b].emplace_back(a, c, G[a].size() - 1);
    }

    // 頂点iのDataを取得
    V get(ll i){
        return res[i];
    }

    void build(vector<V> vVals, vector<V> vids){
        for (int i = 0; i < N; i++) dpused[i].resize(G[i].size(), false), dp[i].resize(G[i].size());

        auto dfs = [&](auto&& dfs, ll now, ll paridx, bool flag) -> V {
            if (paridx != -1 and dpused[now][paridx])
                return dp[now][paridx];
            else if (paridx == -1 and resused[now])
                return res[now];

            // nowが全体の根、または初めの木DPのとき
            if (paridx == -1 or flag) {
                vector<V> A;
                for (ll i = 0; i < G[now].size(); i++) {
                    if (i == paridx) continue;
                    A.emplace_back(rooting(dfs(dfs, G[now][i].to, G[now][i].rev, flag), G[now][i].val));
                }

                // 右からの部分木の累積値
                vector<V> R = vector<V>(N, vids[now]);
                for (ll i = A.size(); i > 0; i--) R[i - 1] = accumul(R[i], A[i - 1]);

                if (paridx == -1) {
                    V L = vids[now];
                    for (ll i = 0; i < G[now].size(); i++) {
                        dpused[now][i] = true;
                        dp[now][i] = apply(merge(L, R[i + 1]), vVals[now]);  //now->to方向の部分木を除いた値
                        // 左から部分木を累積
                        L = accumul(L, A[i]);
                    }
                }

                if (paridx == -1) {
                    resused[now] = true;
                    return res[now] = apply_root(R[0], vVals[now]);
                } else {
                    dpused[now][paridx] = true;
                    return dp[now][paridx] = apply(R[0], vVals[now]);
                }
            }
            // 2回目のdfsで各頂点を根とするとき
            else {
                dfs(dfs, now, -1, flag);
                return dfs(dfs, now, paridx, flag);
            }
        };
        dfs(dfs, 0, -1, true);

        for (ll i = 0; i < N; i++) dfs(dfs, i, -1, false);
    }
};

// 頂点の型
struct vData {
    ll v, size, index;
    // size: 部分木の大きさ
};
// 頂点データの単位元
vData vid = {0, 0, 0};

// 辺の型
struct eData {
    ll v1, v2;
};
// 辺データの単位元
eData eid = {0, 0};

// 累積値に部分木情報を追加
vData accumul(vData acc, vData b){
    acc.v += b.v, acc.size += b.size;
    return acc;
};

// 左からの部分木の累積と右からの累積をマージ
vData merge(vData a, vData b){
    a.v += b.v, a.size += b.size;
    return a;
}

// 1つの部分木情報に辺を適用
vData rooting(vData a, eData e){
    if(a.index == e.v1) {
        // err("eq", a.index, e.v2);
        if(a.index < e.v2) a.v++;
    }else{
        // err("nt", a.index, e.v1);
        if (a.index < e.v1) a.v++;
    }
    // a.v += e.v;
    return a;
}

// マージし終えた頂点で計算
// 1. 根について全ての部分木をマージした後, 各頂点のデータを適用
vData apply_root(vData a, vData f){
    a.size++;
    return a; // ここで部分木のサイズは増える
}
// 2. 根ではない頂点について1つの部分木を除いてマージした後　の2通りに適用
vData apply(vData a, vData f){
    a.size++;
    return a; // ここで部分木のサイズは増える
}

// ReRooting R(N, vid, eid);
// G.build(D); // D: vector<vData> 頂点ごとのデータ
// G.get(i) // 頂点iのvDataを取得


int main() {
    ll N;
    cin >> N;
    ReRooting R(N, vid, eid);
    rep(i, N - 1) {
        ll a, b;
        cin >> a >> b, a--, b--;
        R.add_edge(a, b, {a, b});
    }

    vc<vData> ds(N, vid);
    rep(i, N) ds[i] = {0, 0, i};

    R.build(vc<vData>(N, vid), ds);

    rep(i, N) cout << R.get(i).v << '\n';
}

yukicoder

結果

テストケース

ソースコード