#844500 (C++17) No.1002 Twotone

提出ソース

結果

問題	No.1002 Twotone
ユーザー	👑 rin204
提出日時	2023-02-27 23:33:04
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	2,858 ms / 5,000 ms
コード長	13,646 bytes
コンパイル時間	3,310 ms
コンパイル使用メモリ	255,432 KB
実行使用メモリ	123,824 KB
最終ジャッジ日時	2023-10-13 07:48:18
合計ジャッジ時間	37,651 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,352 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	843 ms 57,424 KB
testcase_04	AC	1,130 ms 73,988 KB
testcase_05	AC	1,147 ms 75,592 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	572 ms 46,220 KB
testcase_08	AC	1,029 ms 77,112 KB
testcase_09	AC	1,008 ms 77,352 KB
testcase_10	AC	2 ms 4,352 KB
testcase_11	AC	1,325 ms 64,044 KB
testcase_12	AC	1,936 ms 81,756 KB
testcase_13	AC	1,923 ms 82,016 KB
testcase_14	AC	2 ms 4,352 KB
testcase_15	AC	853 ms 47,240 KB
testcase_16	AC	1,868 ms 81,436 KB
testcase_17	AC	1,882 ms 81,204 KB
testcase_18	AC	2 ms 4,352 KB
testcase_19	AC	1,511 ms 73,560 KB
testcase_20	AC	1,826 ms 85,984 KB
testcase_21	AC	1,868 ms 85,952 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	1,250 ms 51,324 KB
testcase_24	AC	2,590 ms 86,200 KB
testcase_25	AC	2,534 ms 85,732 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	203 ms 66,132 KB
testcase_28	AC	407 ms 98,112 KB
testcase_29	AC	320 ms 97,404 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	305 ms 96,664 KB
testcase_32	AC	407 ms 97,228 KB
testcase_33	AC	325 ms 96,852 KB
testcase_34	AC	2,858 ms 123,824 KB

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

ソースコード

raw source code

#line 1 "A.cpp"
// #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 ull = unsigned long long;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));

#ifndef RIN__LOCAL
#define endl "\n"
#endif
#define spa ' '
#define len(A) A.size()
#define all(A) begin(A), end(A)

#define fori1(a) for(ll _ = 0; _ < (a); _++)
#define fori2(i, a) for(ll i = 0; i < (a); i++)
#define fori3(i, a, b) for(ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

template <typename T>
vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){
    vector<tuple<ll, T>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){
    vector<tuple<ll, char>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

#define enum1(A) fori(A.size())
#define enum2(a, A) for(auto a:A)
#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))
#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))
#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)

template <typename T, typename S>
vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){
    int n = min(A.size(), B.size());
    vector<tuple<T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};
    return ret;
}

template <typename T, typename S>
vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){
    int n = min(A.size(), B.size());
    vector<tuple<ll, T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};
    return ret;
}

#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))
#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))
#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))
#define overload6(a, b, c, d, e, f, g, ...) g
#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)

vector<char> stoc(string &S){
    int n = S.size();
    vector<char> ret(n);
    for(int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}

#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);

const ll MOD1 = 1000000007;
const ll MOD9 = 998244353;

template<class T> auto min(const T& a){
    return *min_element(all(a));
}
template<class T> auto max(const T& a){
    return *max_element(all(a));
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

void FLUSH(){cout << flush;}
void print(){cout << endl;}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(forward<Tail>(tail)...);
}
template<typename T>
void print(vector<T> &A){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i != n - 1) cout << ' ';
    }
    cout << endl;
}
template<typename T>
void print(vector<vector<T>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void print(pair<T, S> &A){
    cout << A.first << spa << A.second << endl;
}
template<typename T, typename S>
void print(vector<pair<T, S>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void prisep(vector<T> &A, S sep){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i == n - 1) cout << endl;
        else cout << sep;
    }
}
template<typename T, typename S>
void priend(T A, S end){
    cout << A << end;
}
template<typename T>
void priend(T A){
    priend(A, spa);
}
template<class... T>
void inp(T&... a){
    (cin >> ... >> a);
}
template<typename T>
void inp(vector<T> &A){
    for(auto &a:A) cin >> a;
}
template<typename T>
void inp(vector<vector<T>> &A){
    for(auto &row:A) inp(row);
}
template<typename T, typename S>
void inp(pair<T, S> &A){
    inp(A.first, A.second);
}
template<typename T, typename S>
void inp(vector<pair<T, S>> &A){
    for(auto &row: A) inp(row.first, row.second);
}

template<typename T>
T sum(vector<T> &A){
    T tot = 0;
    for(auto a:A) tot += a;
    return tot;
}

template<typename T>
pair<vector<T>, map<T, int>> compression(vector<T> X){
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    map<T, int> mp;
    for(int i = 0; i < X.size(); i++) mp[X[i]] = i;
    return {X, mp};
}

#line 2 "Library/C++/tree/CentroidDecomposition.hpp"

struct CentroidDecomposition{
public:
    int n;
    vector<int> par; // 重心分解した木の直接の親
    vector<int> depth; // 重心分解した木の深さ
    vector<int> size; // 頂点iを重心とする木のサイズ
    vector<int> childcnt; // 頂点iの子の個数
    vector<vector<int>> pars; // pars[i][j] := 頂点iの先祖のうち，深さがjである頂点
    vector<vector<int>> edges;
    vector<vector<int>> centroids; // centroids[i] := 深さiの重心の一覧
    vector<vector<int>> treeind; // treeind[i][j] := 頂点jが深さiの重心の何番目の部分木か
    vector<vector<int>> cent_depth; // cent_depth[i][j] := 頂点jと深さiの重心からの距離

    CentroidDecomposition() = default;
    CentroidDecomposition(int n) : n(n){
        edges.resize(n);
        pars.resize(n);
        childcnt.resize(n);
        par.assign(n, -1);
        depth.assign(n, -1);
        size.assign(n, -1);
    }

    void add_edge(int u, int v){
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void read_edges(int indexed=1, int m=-1){
        if(m == -1) m = n - 1;
        while(m--){
            int u, v;
            cin >> u >> v;
            add_edge(u - indexed, v - indexed);
        }
    }

    void build(){
        dfs(0, -1);
    }

    pair<vector<vector<vector<int>>>, vector<vector<int>>> dist_freq(){
        vector<vector<vector<int>>> dist(n);
        vector<vector<int>> disttot(n);
        for(int i = 0; i < n; i++){
            stack<pair<int, pair<int, int>>> st;
            disttot[i] = {1};
            dist[i].assign(childcnt[i], {0});
            st.push({0, {i, -1}});
            while(!st.empty()){
                int d = st.top().first + 1;
                int pos = st.top().second.first;
                int bpos = st.top().second.second;
                st.pop();
                for(auto npos:edges[pos]){
                    if(npos == bpos || depth[npos] < depth[i]) continue;
                    st.push({d, {npos, pos}});
                    
                    if(disttot[i].size() == d) disttot[i].push_back(1);
                    else disttot[i][d]++;

                    int j = treeind[depth[i]][npos];
                    if(dist[i][j].size() == d) dist[i][j].push_back(1);
                    else dist[i][j][d]++;
                }
            }
        }
        return {dist, disttot};
    }

        pair<vector<vector<vector<long long>>>, vector<vector<long long>>> dist_freq_ll(){
        vector<vector<vector<long long>>> dist(n);
        vector<vector<long long>> disttot(n);
        for(int i = 0; i < n; i++){
            stack<pair<int, pair<int, int>>> st;
            disttot[i] = {1};
            dist[i].assign(childcnt[i], {0});
            st.push({0, {i, -1}});
            while(!st.empty()){
                int d = st.top().first + 1;
                int pos = st.top().second.first;
                int bpos = st.top().second.second;
                st.pop();
                for(auto npos:edges[pos]){
                    if(npos == bpos || depth[npos] < depth[i]) continue;
                    st.push({d, {npos, pos}});
                    
                    if(disttot[i].size() == d) disttot[i].push_back(1);
                    else disttot[i][d]++;

                    int j = treeind[depth[i]][npos];
                    if(dist[i][j].size() == d) dist[i][j].push_back(1);
                    else dist[i][j][d]++;
                }
            }
        }
        return {dist, disttot};
    }

    vector<tuple<int, int, int>> cent_ind_dist(int u){
        vector<tuple<int, int, int>> ret; // uの親 + u の各重心の {頂点番号，何番目の部分木か，距離}
        int d = 0;
        for(auto p:pars[u]){
            ret.push_back({p, treeind[d][u], cent_depth[d][u]});
            d++;
        }
        ret.push_back({u, -1, 0});
        return ret;
    };

private:
    void dfs(int pos, int bpos, int d=0, int c=-1){
        stack<int> st;
        st.push(pos);
        stack<int> route;
        int sz = 0;
        if(treeind.size() <= d) treeind.push_back(vector<int>(n, -1));
        if(cent_depth.size() <= d) cent_depth.push_back(vector<int>(n, -1));
        if(d != 0) cent_depth[d - 1][pos] = 1;
        while(!st.empty()){
            int pos = st.top();
            st.pop();
            if(bpos != -1) pars[pos].push_back(bpos);
            depth[pos] = -2;
            route.push(pos);
            sz++;
            if(d >= 1) treeind[d - 1][pos] = c;
            for(auto npos:edges[pos]){
                if(depth[npos] == -1){
                    st.push(npos);
                    if(d != 0) cent_depth[d - 1][npos] = cent_depth[d - 1][pos] + 1;
                }
            }
        }

        int g = -1;
        while(!route.empty()){
            int pos = route.top();
            route.pop();
            size[pos] = 1;
            depth[pos] = -1;
            bool isg = true;
            for(auto npos:edges[pos]){
                if(depth[npos] == -1){
                    size[pos] += size[npos];
                    if(size[npos] * 2 > sz) isg = false;
                }
            }
            if(isg && 2 * size[pos] >= sz){
                g = pos;
            }
        }

        if(centroids.size() == d) centroids.push_back({g});
        else centroids[d].push_back(g);
        size[g] = sz;
        par[g] = bpos;
        depth[g] = d;
        cent_depth[d][g] = 0;
        if(sz != 1){
            int c = 0;
            for(auto npos:edges[g]){
                if(depth[npos] == -1) dfs(npos, g, d + 1, c++);
            }
            childcnt[g] = c;
        }
    }
};
#line 188 "A.cpp"

void solve(){
    INT(n);
    LL(k);
    CentroidDecomposition G(n);
    using P = pair<int, ll>;
    vvec(P, edges, n);
    fori(i, n - 1){
        INT(u, v, c);
        u--; v--;
        edges[u].push_back({v, c});
        edges[v].push_back({u, c});
        G.add_edge(u, v);
    }
    k++;
    G.build();
    ll ans = 0;
    for(int d = 0; d < G.centroids.size(); d++){
        vec(bool, used, n, false);
        for(auto g:G.centroids[d]){
            map<ll, int> cnt;
            vector<map<ll, int>> subcnt(G.childcnt[g]);
            stack<P> st;
            st.push({g, 0});
            while(!st.empty()){
                int pos = st.top().first;
                ll h = st.top().second;
                st.pop();
                used[pos] = true;
                for(auto &[npos, c]: edges[pos]){
                    if(used[npos] || G.depth[npos] < d) continue;
                    ll nh;
                    if(h == 0 || h == c){
                        nh = c;
                        int p = G.treeind[d][npos];
                        ans += cnt[-1]++;
                        ans -= subcnt[p][-1]++;
                        ans -= cnt[nh]++;
                        ans += subcnt[p][nh]++;
                        ans += cnt[k * k + c];
                        ans -= subcnt[p][k * k + c];
                    }
                    else if(h >= k && c != h % k && c != h / k) continue;
                    else{
                        int hh;
                        if(h < k){
                            if(h < c) nh = h * k + c;
                            else nh = c * k + h;
                            hh = h;
                        }
                        else{
                            nh = h;
                            hh = h / k;
                            if(hh == c) hh = h - c * k;
                        }
                        if(!cnt.count(nh)) cnt[nh] = 1;
                        int p = G.treeind[d][npos];
                        ans += cnt[nh]++;
                        ans -= subcnt[p][nh]++;
                        ans += cnt[hh] + cnt[c];
                        ans -= subcnt[p][hh] + subcnt[p][c];

                        cnt[k * k + hh]++;
                        cnt[k * k + c]++;
                        subcnt[p][k * k + hh]++;
                        subcnt[p][k * k + c]++;
                    }
                    st.push({npos, nh});
                }
            }
        }
    }
    print(ans);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード