結果
問題 | No.828 全方位神童数 |
ユーザー | kopricky |
提出日時 | 2019-04-13 07:52:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,000 ms |
コード長 | 9,908 bytes |
コンパイル時間 | 848 ms |
コンパイル使用メモリ | 76,212 KB |
実行使用メモリ | 29,824 KB |
最終ジャッジ日時 | 2024-06-10 06:11:39 |
合計ジャッジ時間 | 6,469 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,064 KB |
testcase_01 | AC | 4 ms
8,064 KB |
testcase_02 | AC | 4 ms
8,192 KB |
testcase_03 | AC | 11 ms
9,088 KB |
testcase_04 | AC | 6 ms
8,448 KB |
testcase_05 | AC | 10 ms
8,960 KB |
testcase_06 | AC | 5 ms
8,448 KB |
testcase_07 | AC | 5 ms
8,320 KB |
testcase_08 | AC | 5 ms
8,320 KB |
testcase_09 | AC | 5 ms
8,320 KB |
testcase_10 | AC | 9 ms
8,704 KB |
testcase_11 | AC | 5 ms
8,448 KB |
testcase_12 | AC | 8 ms
8,832 KB |
testcase_13 | AC | 52 ms
15,104 KB |
testcase_14 | AC | 115 ms
22,528 KB |
testcase_15 | AC | 39 ms
13,440 KB |
testcase_16 | AC | 53 ms
15,488 KB |
testcase_17 | AC | 42 ms
13,952 KB |
testcase_18 | AC | 78 ms
18,304 KB |
testcase_19 | AC | 145 ms
25,856 KB |
testcase_20 | AC | 92 ms
20,096 KB |
testcase_21 | AC | 130 ms
23,424 KB |
testcase_22 | AC | 29 ms
11,776 KB |
testcase_23 | AC | 13 ms
9,472 KB |
testcase_24 | AC | 79 ms
17,280 KB |
testcase_25 | AC | 34 ms
12,032 KB |
testcase_26 | AC | 166 ms
24,576 KB |
testcase_27 | AC | 140 ms
22,272 KB |
testcase_28 | AC | 169 ms
24,576 KB |
testcase_29 | AC | 157 ms
23,680 KB |
testcase_30 | AC | 81 ms
17,152 KB |
testcase_31 | AC | 79 ms
17,024 KB |
testcase_32 | AC | 168 ms
24,320 KB |
testcase_33 | AC | 181 ms
25,728 KB |
testcase_34 | AC | 130 ms
22,400 KB |
testcase_35 | AC | 88 ms
17,792 KB |
testcase_36 | AC | 110 ms
20,224 KB |
testcase_37 | AC | 77 ms
16,000 KB |
testcase_38 | AC | 101 ms
18,944 KB |
testcase_39 | AC | 157 ms
24,576 KB |
testcase_40 | AC | 71 ms
15,872 KB |
testcase_41 | AC | 60 ms
14,720 KB |
testcase_42 | AC | 181 ms
25,984 KB |
testcase_43 | AC | 79 ms
29,824 KB |
testcase_44 | AC | 34 ms
16,640 KB |
testcase_45 | AC | 46 ms
20,992 KB |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#define ll long long#define INF 1000000005#define MOD 1000000007#define EPS 1e-10#define rep(i,n) for(int i=0;i<(int)(n);++i)#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)#define each(a,b) for(auto& (a): (b))#define all(v) (v).begin(),(v).end()#define len(v) (int)(v).size()#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())#define cmx(x,y) x=max(x,y)#define cmn(x,y) x=min(x,y)#define fi first#define se second#define pb push_back#define show(x) cout<<#x<<" = "<<(x)<<endl#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endlusing namespace std;typedef pair<int,int> P;typedef pair<ll,ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<double> vd;typedef vector<P> vp;typedef vector<string> vs;#define MUL 1000000const int MAX_N = 200005;#define getchar getchar_unlocked#define putchar putchar_unlockedinline int in() {int n, c;while ((c = getchar()) < '0') if (c == EOF) return -1;n = c - '0';while ((c = getchar()) >= '0') n = n * 10 + c - '0';return n;}inline void out(int n) {int res[11], i = 0;do { res[i++] = n % 10, n /= 10; } while (n);while (i) putchar(res[--i] + '0');putchar('\n');}template<typename KeyType, typename ValueType> class node {public:using KT = KeyType;using VT = ValueType;KT key;int sz;VT value, al, lazy;node *left, *right, *par;node(KT _key, VT _value) : key(_key), sz(1), value(_value), al(id2), lazy(id1),left(nullptr), right(nullptr), par(nullptr){}static const VT id1 = (VT)0;static const VT id2 = (VT)0;void opr1(VT& arg1, const VT arg2) const {arg1 = (arg1 + arg2) % MOD;}VT opr2(const VT arg1, const VT arg2) const {return (arg1 + arg2) % MOD;}bool isRoot() const {return !par;}void push(){if(lazy != id1){opr1(value, lazy), al += lazy;if(left) opr1(left->lazy, lazy);if(right) opr1(right->lazy, lazy);lazy = id1;}}void eval(){sz = 1, al = value;if(left) left->push(), sz += left->sz, al = opr2(left->al, al);if(right) right->push(), sz += right->sz, al = opr2(al, right->al);}void rotate(bool right_){node<KT, VT> *p = par, *g = p->par;if(right_){if((p->left = right)) right->par = p;right = p, p->par = this;}else{if((p->right = left)) left->par = p;left = p, p->par = this;}p->eval(), eval();if(!(par = g)) return;if(g->left == p) g->left = this;if(g->right == p) g->right = this;g->eval();}};// 頂点 u を木の根にするtemplate<typename KT, typename VT>node<KT, VT>* splay(node<KT, VT>* u){if(!u) return nullptr;while(!(u->isRoot())){node<KT, VT> *p = u->par, *gp = p->par;if(p->isRoot()){ // zigp->push(), u->push();u->rotate((u == p->left));}else{gp->push(), p->push(), u->push();bool flag = (u == p->left);if((u == p->left) == (p == gp->left)){ // zig-zigp->rotate(flag), u->rotate(flag);}else{ // zig-zagu->rotate(flag), u->rotate(!flag);}}}u->push();return u;}// 存在しない key の場合何が返ってくるかは不定template<typename KT, typename VT>pair<node<KT, VT>*, bool> find(const KT _key, node<KT, VT>* root){node<KT, VT> *cur = nullptr, *nx = root;while(nx){cur = nx, cur->push();if(cur->key == _key) break;if(cur->key > _key) nx = cur->left;else nx = cur->right;}return make_pair(splay(cur), cur && cur->key == _key);}// root を根とする木の頂点でキーが _key 以上で最小のものを返す(bool は _key 以上のものがあるかないか)// _key 以上のものがなくても返り値のノードは nullptr とは限らないことに注意(_key 以上がなくても木の根は変わるので)template<typename KT, typename VT>pair<node<KT, VT>*, bool> lower_bound(const KT _key, node<KT, VT>* root){node<KT, VT> *cur = nullptr, *nx = root, *res = nullptr;while(nx){cur = nx, cur->push();if(cur->key >= _key){nx = cur->left;if(!res || cur->key <= res->key) res = cur;}else nx = cur->right;}node<KT, VT>* tmp = splay(cur);return res ? make_pair(splay(res), res) : make_pair(tmp, res);}// root を根とする木の頂点でキーが _key を超える最小のものを返す(bool は _key を超えるものがあるかないか)// _key を超えるものがなくても返り値のノードは nullptr とは限らないことに注意(_key を超えるものがなくても木の根は変わるので)template<typename KT, typename VT>pair<node<KT, VT>*, bool> upper_bound(const KT _key, node<KT, VT>* root){node<KT, VT> *cur = nullptr, *nx = root, *res = nullptr;while(nx){cur = nx, cur->push();if(cur->key > _key){nx = cur->left;if(!res || cur->key <= res->key) res = cur;}else nx = cur->right;}node<KT, VT>* tmp = splay(cur);return res ? make_pair(splay(res), res) : make_pair(tmp, res);}// root1 を根とする木のすべての要素が root 2 を根とする木のすべての要素より小さいときの mergetemplate<typename KT, typename VT>node<KT, VT>* join(node<KT, VT>* root1, node<KT, VT>* root2){if(!root1 || !root2) return root1 ? root1 : root2;node<KT, VT> *cur = nullptr, *nx = root1;while(nx){cur = nx, cur->push(), nx = cur->right;}node<KT, VT>* ver = splay(cur);ver->right = root2, ver->eval(), root2->par = ver;return ver;}// root を根とする木に ver を insert するtemplate<typename KT, typename VT>node<KT, VT>* insert(node<KT, VT>* ver, node<KT, VT>* root){if(!root) return ver;node<KT, VT> *cur = nullptr, *nx = root;while(nx){cur = nx, cur->push();if(cur->key > ver->key) nx = cur->left;else nx = cur->right;}if(cur->key > ver->key) cur->left = ver, ver->par = cur;else cur->right = ver, ver->par = cur;cur->eval();return splay(ver);}// root を根とする木から _key をキーとする要素を erase する(同一キーの要素が複数ある場合はどれかひとつだけ消す)// _key をキーとする要素がない場合は第 2 引数として false を返す.template<typename KT, typename VT>pair<node<KT, VT>*, bool> erase(const KT _key, node<KT, VT>* root){pair<node<KT, VT>*, bool> ver = find(_key, root);if(!ver.second) return ver;return make_pair(join(ver.first->left, ver.first->right), true);}// root1 を根とする木と root 2 を根とする木の mergetemplate<typename KT, typename VT>node<KT, VT>* merge(node<KT, VT>* root1, node<KT, VT>* root2){if(!root2) return root1;return insert(root2, root1);}// root を根とする木を (_key 未満, _key 以上) の木に split する.template<typename KT, typename VT>pair<node<KT, VT>*, node<KT, VT>*> split(const KT _key, node<KT, VT>* root){pair<node<KT, VT>*, bool> res = lower_bound(_key, root);if(!res.second) return make_pair(res.first, nullptr);node<KT, VT> *res1 = nullptr, *res2 = res.first;res1 = res2->left, res2->left = nullptr, res2->eval();if(res1) res1->par = nullptr;return make_pair(res1, res2);}// root を根とする木のうちキー値が [lvalue, rvalue) のものに対して x の更新を行う.template<typename KT, typename VT>node<KT, VT>* range(KT lvalue, KT rvalue, VT x, node<KT, VT>* root){auto pnn1 = split(lvalue, root);auto pnn2 = split(rvalue, pnn1.second);if(pnn2.first) opr1(pnn2.first->lazy, x);return join(pnn1.first, join(pnn2.first, pnn2.second));}// root を根とする木のうちキー値が [lvalue, rvalue) のものに対するクエリに答える.// 返り値は(木の根, 値)template<typename KT, typename VT>pair<node<KT, VT>*, VT> query(KT lvalue, KT rvalue, node<KT, VT>* root){auto pnn1 = split(lvalue, root);auto pnn2 = split(rvalue, pnn1.second);VT res = (pnn2.first ? pnn2.first->al : node<KT, VT>::id2);return make_pair(join(pnn1.first, join(pnn2.first, pnn2.second)), res);}vector<int> G[MAX_N];int ans[MAX_N];node<int, int>* ptr[MAX_N];void dfs(node<int, int>* cur){cur->push();ans[cur->key] += cur->value;if(cur->left) dfs(cur->left);if(cur->right) dfs(cur->right);}int main(){cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;rep(i,n){cin >> ans[i];}rep(i,n-1){int u, v;cin >> u >> v;if(u > v) swap(u, v);G[v-1].pb(u-1);}rep(i,n){ptr[i] = new node<int, int>(i, 1);each(v,G[i]){splay(ptr[v]), ptr[v]->lazy += 1;merge(ptr[v], ptr[i]);}}dfs(ptr[n-1]);int ret = 1;rep(i,n){ret = (ll)ret * ans[i] % MOD;}cout << ret << "\n";return 0;}