結果
| 問題 | No.828 全方位神童数 |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-05-02 03:03:19 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 4,284 bytes |
| コンパイル時間 | 1,055 ms |
| コンパイル使用メモリ | 83,600 KB |
| 実行使用メモリ | 5,272 KB |
| 最終ジャッジ日時 | 2023-08-30 04:35:02 |
| 合計ジャッジ時間 | 12,447 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
コンパイルメッセージ
次のファイルから読み込み: /usr/local/gcc7/include/c++/12.2.0/vector:64,
次から読み込み: main.cpp:1:
静的メンバ関数 ‘static std::vector<_Tp, _Alloc>::size_type std::vector<_Tp, _Alloc>::_S_check_init_len(size_type, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]’ 内,
inlined from ‘std::vector<_Tp, _Alloc>::vector(size_type, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]’ at /usr/local/gcc7/include/c++/12.2.0/bits/stl_vector.h:552:47,
inlined from ‘int main()’ at main.cpp:81:24:
/usr/local/gcc7/include/c++/12.2.0/bits/stl_vector.h:1904:9: 警告: ‘N’ is used uninitialized [-Wuninitialized]
1904 | if (__n > _S_max_size(_Tp_alloc_type(__a)))
| ^~
main.cpp: 関数 ‘int main()’ 内:
main.cpp:80:17: 備考: ‘N’ はここで定義されています
80 | std::size_t N;
| ^
ソースコード
#include <vector>
#include <iostream>
#include <cassert>
#include <numeric>
//!=================================================!//
//! .88888. dP !//
//! d8' '88 88 !//
//! 88 88d888b. .d8888b. 88d888b. 88d888b. !//
//! 88 YP88 88' '88 88' '88 88' '88 88' '88 !//
//! Y8. .88 88 88. .88 88. .88 88 88 !//
//! '88888' dP '88888P8 88Y888P' dP dP !//
//! 88 !//
//! dP !//
//!=================================================!//
struct Graph
{
Graph(const std::size_t v) : V{v}, edge(v), rev_edge(v) {}
void addEdge(const std::size_t from, const std::size_t to, const bool bi = false)
{
assert(from < V), assert(to < V);
edge[from].push_back(to), rev_edge[to].push_back(from);
if (bi) { addEdge(to, from, false); }
}
const std::vector<std::size_t>& operator[](const std::size_t i) const { return assert(i < V), edge[i]; }
friend std::ostream& operator<<(std::ostream& os, const Graph& g)
{
os << "[\n";
for (std::size_t i = 0; i < g.V; i++) {
for (const std::size_t to : g.edge[i]) { os << i << "->" << to << "\n"; }
}
return (os << "]\n");
}
std::size_t V;
std::vector<std::vector<std::size_t>> edge, rev_edge;
};
//!==============================================================================!//
//! dP dP oo 88888888b oo dP !//
//! 88 88 88 88 !//
//! 88 88 88d888b. dP .d8888b. 88d888b. a88aaaa dP 88d888b. .d888b88 !//
//! 88 88 88' '88 88 88' '88 88' '88 88 88 88' '88 88' '88 !//
//! Y8. .8P 88 88 88 88. .88 88 88 88 88 88 88 88. .88 !//
//! 'Y88888P' dP dP dP '88888P' dP dP dP dP dP dP '88888P8 !//
//!==============================================================================!//
class UnionFind
{
public:
UnionFind(const std::size_t v) : V(v), parent(v), size(v, 1) { std::iota(parent.begin(), parent.end(), 0); }
std::size_t find(const std::size_t a) { return assert(a < V), parent[a] == a ? a : parent[a] = find(parent[a]); }
bool same(const std::size_t a, const std::size_t b)
{
assert(a < V), assert(b < V);
return find(a) == find(b);
}
void unite(std::size_t a, std::size_t b)
{
assert(a < V), assert(b < V);
a = find(a), b = find(b);
if (a == b) { return; }
if (size[a] < size[b]) { std::swap(a, b); }
size[a] += size[b], parent[b] = a;
}
std::size_t getSize(const std::size_t a) { return assert(a < V), size[find(a)]; }
friend std::ostream& operator<<(std::ostream& os, const UnionFind& uf)
{
os << "[";
for (std::size_t i = 0; i < uf.parent.size(); i++) { os << uf.parent[i] << (i + 1 == uf.parent.size() ? "" : ","); }
return (os << "]\n");
}
private:
const std::size_t V;
std::vector<std::size_t> parent, size;
};
int main()
{
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
using ll = long long;
constexpr ll MOD = 1000000007;
std::size_t N;
std::vector<ll> r(N);
for (std::size_t i = 0; i < N; i++) { std::cin >> r[i]; }
Graph T(N);
for (std::size_t i = 0; i < N - 1; i++) {
std::size_t u, v;
std::cin >> u >> v, u--, v--;
T.addEdge(u, v, true);
}
UnionFind uf(N);
std::vector<std::size_t> top(N);
std::iota(top.begin(), top.end(), 0);
Graph T2(N);
for (std::size_t i = 0; i < N; i++) {
for (const std::size_t to : T[i]) {
if (to > i) { continue; }
const std::size_t rep = uf.find(to);
T2.addEdge(i, top[rep]);
uf.unite(i, rep);
top[uf.find(i)] = i;
}
}
ll ans = 1;
auto dfs = [&](auto&& self, const std::size_t s, const ll d) -> void {
(ans *= (r[s] + d)) %= MOD;
for (const std::size_t to : T2[s]) { self(self, to, d + 1); }
};
dfs(dfs, 0, 1LL);
std::cout << ans << std::endl;
return 0;
}