結果

問題 No.1103 Directed Length Sum
ユーザー AtamaokaCAtamaokaC
提出日時 2020-07-03 22:15:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,387 ms / 3,000 ms
コード長 3,707 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 213,640 KB
実行使用メモリ 117,448 KB
最終ジャッジ日時 2024-09-17 02:58:15
合計ジャッジ時間 15,247 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 754 ms
100,940 KB
testcase_03 AC 900 ms
117,448 KB
testcase_04 AC 751 ms
58,240 KB
testcase_05 AC 1,387 ms
98,432 KB
testcase_06 AC 464 ms
38,912 KB
testcase_07 AC 90 ms
11,800 KB
testcase_08 AC 149 ms
16,512 KB
testcase_09 AC 54 ms
8,632 KB
testcase_10 AC 214 ms
21,248 KB
testcase_11 AC 820 ms
63,104 KB
testcase_12 AC 469 ms
39,424 KB
testcase_13 AC 221 ms
21,708 KB
testcase_14 AC 41 ms
7,424 KB
testcase_15 AC 349 ms
31,372 KB
testcase_16 AC 930 ms
70,656 KB
testcase_17 AC 1,000 ms
73,568 KB
testcase_18 AC 207 ms
21,256 KB
testcase_19 AC 825 ms
64,784 KB
testcase_20 AC 65 ms
9,732 KB
testcase_21 AC 127 ms
15,124 KB
testcase_22 AC 667 ms
53,692 KB
testcase_23 AC 373 ms
33,392 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