結果

問題 No.1103 Directed Length Sum
ユーザー AtamaokaCAtamaokaC
提出日時 2020-07-03 22:15:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,299 ms / 3,000 ms
コード長 3,707 bytes
コンパイル時間 2,701 ms
コンパイル使用メモリ 215,188 KB
実行使用メモリ 117,516 KB
最終ジャッジ日時 2023-10-17 04:15:14
合計ジャッジ時間 15,673 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 734 ms
100,968 KB
testcase_03 AC 876 ms
117,516 KB
testcase_04 AC 725 ms
58,156 KB
testcase_05 AC 1,299 ms
98,396 KB
testcase_06 AC 466 ms
38,960 KB
testcase_07 AC 94 ms
11,912 KB
testcase_08 AC 154 ms
16,332 KB
testcase_09 AC 54 ms
8,812 KB
testcase_10 AC 220 ms
21,280 KB
testcase_11 AC 803 ms
63,104 KB
testcase_12 AC 463 ms
39,488 KB
testcase_13 AC 228 ms
21,808 KB
testcase_14 AC 42 ms
7,328 KB
testcase_15 AC 355 ms
31,440 KB
testcase_16 AC 907 ms
70,624 KB
testcase_17 AC 942 ms
73,460 KB
testcase_18 AC 217 ms
21,280 KB
testcase_19 AC 818 ms
64,688 KB
testcase_20 AC 70 ms
9,868 KB
testcase_21 AC 136 ms
15,276 KB
testcase_22 AC 666 ms
53,472 KB
testcase_23 AC 384 ms
33,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef unsigned long long int ullint;
std::string YesNo[] = {"No","Yes"};
#define loop(i,N) for(int i=0; i<(N); i++)
template<typename T>
auto sort_all(T& v) { return std::sort(v.begin(),v.end()); }
template<typename T>
auto sum_all(const T& v) { auto z = v[0]; z = 0;
    return std::accumulate(v.begin(),v.end(),z); }
template<typename T>
auto input( std::size_t N,
            const std::vector<T>& head={},
            const std::vector<T>& tail={}) {
    auto s = head.size();
    auto t = tail.size();
    std::vector<T> v;
    v.reserve(s+N+t);
    v.insert(v.end(), head.begin(), head.end());
    v.resize(s+N);
    loop(i,N) std::cin >> v[s+i];
    v.insert(v.end(), tail.begin(), tail.end());
    return std::move(v);
}
class range {
    typedef int Int;
    Int start, stop, step;
    void initialize() {
        auto sign = (step >= 0) ? 1 : -1;
        stop = start + ((stop-start-sign)/step + 1) * step;
        if ((stop-start) * step <= 0) stop = start;
    }
public:
    range(Int start, Int stop, Int step=1) : start(start), stop(stop), step(step) {
        initialize();
    }
    range(Int stop) : start(0), stop(stop), step(1) { initialize(); }
    struct iterator {
        Int i, step;
        Int& operator*() { return i; }
        iterator& operator++() { i += step; return *this; }
        bool operator!=(const iterator& v) { return i != v.i; }
    };
    iterator begin() { return {start, step}; }
    iterator end()   { return {stop, step}; }
};
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x)
{
    return std::make_pair(-x.first, -x.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator+(
    const std::pair<T1,T2>& x,
    const std::pair<T1,T2>& y)
{
    return std::make_pair(x.first+y.first, x.second+y.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x + (-y);
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator+=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    x.first += y.first;
    x.second += y.second;
    return x;
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator-=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x += (-y);
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& cout, const std::pair<T1,T2>& data)
{
    cout << "(" << data.first << ", " << data.second << ")";
    return cout;
}
template<typename T>
std::ostream& operator<<(std::ostream& cout, const std::vector<T>& data)
{
    cout << "[";
    if (data.size() == 0) {}
    else if (data.size() == 1) { cout << data[0]; } 
    else {
        cout << data[0];
        for (auto itr=data.begin()+1; itr!=data.end(); ++itr) {
            cout << ", " << *itr;
        }
    }
    cout << "]";
    return cout;
}

typedef llint Int;

Int MOD = 1000000000 + 7;

int main(void)
{
    Int N;
    cin >> N;
    auto children = vector<set<int>>(N);
    auto parent = vector<int>(N,-1);

    for (auto i : range(N-1)) {
        int A, B;
        cin >> A >> B;
        A -= 1; B -= 1;
        children[A].insert(B);
        parent[B] = A;
    }

    auto root = distance(parent.begin(), find(parent.begin(),parent.end(),-1));
    Int ans = 0;
    vector<pair<int,Int>> pool({{root,0}});
    while (pool.size()) {
        auto p = pool.back();
        pool.pop_back();
        auto node = p.first;
        auto d = p.second;
        ans += d * (d+1) / 2;
        ans %= MOD;
        for (auto c : children[node]) {
            pool.push_back({c, d+1});
        }
    }
    cout << ans << endl;

    return 0;
}
0