結果
問題 | No.828 全方位神童数 |
ユーザー | kopricky |
提出日時 | 2019-04-13 07:03:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 7,769 bytes |
コンパイル時間 | 1,824 ms |
コンパイル使用メモリ | 169,180 KB |
実行使用メモリ | 27,496 KB |
最終ジャッジ日時 | 2023-08-30 05:40:45 |
合計ジャッジ時間 | 7,843 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,436 KB |
testcase_01 | AC | 4 ms
8,416 KB |
testcase_02 | AC | 4 ms
8,396 KB |
testcase_03 | AC | 10 ms
9,380 KB |
testcase_04 | AC | 6 ms
8,832 KB |
testcase_05 | AC | 10 ms
9,228 KB |
testcase_06 | AC | 6 ms
8,612 KB |
testcase_07 | AC | 5 ms
8,784 KB |
testcase_08 | AC | 5 ms
8,560 KB |
testcase_09 | AC | 4 ms
8,452 KB |
testcase_10 | AC | 8 ms
9,060 KB |
testcase_11 | AC | 4 ms
8,452 KB |
testcase_12 | AC | 9 ms
9,064 KB |
testcase_13 | AC | 68 ms
15,384 KB |
testcase_14 | AC | 165 ms
22,784 KB |
testcase_15 | AC | 45 ms
13,500 KB |
testcase_16 | AC | 66 ms
15,752 KB |
testcase_17 | AC | 49 ms
14,132 KB |
testcase_18 | AC | 106 ms
18,668 KB |
testcase_19 | AC | 197 ms
25,692 KB |
testcase_20 | AC | 105 ms
20,672 KB |
testcase_21 | AC | 150 ms
23,576 KB |
testcase_22 | AC | 29 ms
12,284 KB |
testcase_23 | AC | 12 ms
9,588 KB |
testcase_24 | AC | 88 ms
17,508 KB |
testcase_25 | AC | 36 ms
12,296 KB |
testcase_26 | AC | 203 ms
24,468 KB |
testcase_27 | AC | 159 ms
22,344 KB |
testcase_28 | AC | 201 ms
24,576 KB |
testcase_29 | AC | 184 ms
23,720 KB |
testcase_30 | AC | 90 ms
17,468 KB |
testcase_31 | AC | 88 ms
17,180 KB |
testcase_32 | AC | 193 ms
24,460 KB |
testcase_33 | AC | 225 ms
25,876 KB |
testcase_34 | AC | 163 ms
22,472 KB |
testcase_35 | AC | 98 ms
18,040 KB |
testcase_36 | AC | 129 ms
20,228 KB |
testcase_37 | AC | 78 ms
16,264 KB |
testcase_38 | AC | 115 ms
19,332 KB |
testcase_39 | AC | 203 ms
24,576 KB |
testcase_40 | AC | 79 ms
16,224 KB |
testcase_41 | AC | 69 ms
14,952 KB |
testcase_42 | AC | 223 ms
26,068 KB |
testcase_43 | AC | 78 ms
27,496 KB |
testcase_44 | AC | 33 ms
15,876 KB |
testcase_45 | AC | 47 ms
19,680 KB |
ソースコード
#include <bits/stdc++.h> #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 sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl using namespace std; template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";} template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;} template<typename S,typename T,typename U> auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;} template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>m){for(auto&e:m)o<<e<<" ";return o;} template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;} void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);} typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<P> vp; typedef vector<double> vd; typedef vector<string> vs; const int MAX_N = 200005; 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 += arg2; } VT opr2(const VT arg1, const VT arg2) const { return arg1 + arg2; } 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(); } }; 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()){ // zig p->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-zig p->rotate(flag), u->rotate(flag); }else{ // zig-zag u->rotate(flag), u->rotate(!flag); } } } u->push(); return u; } // 存在しない key の場合何が返ってくるかは不定 template<typename KT, typename VT> node<KT, VT>* 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 splay(cur); } template<typename KT, typename VT> node<KT, VT>* 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; } return splay(res); } template<typename KT, typename VT> node<KT, VT>* 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; } return splay(cur); } template<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; } 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); } template<typename KT, typename VT> node<KT, VT>* erase(const KT _key, node<KT, VT>* root){ node<KT, VT>* ver = find(_key, root); return join(ver->left, ver->right); } template<typename KT, typename VT> node<KT, VT>* merge(node<KT, VT>* root1, node<KT, VT>* root2){ if(!root2) return root1; return insert(root2, root1); } template<typename KT, typename VT> pair<node<KT, VT>*, node<KT, VT>*> split(const KT _key, node<KT, VT>* root){ node<KT, VT> *res1 = nullptr, *res2 = lower_bound(_key, root); if(res2) res1 = res2->left, res2->left = nullptr, res2->eval(); else return make_pair(root, nullptr); if(res1) res1->par = nullptr; return make_pair(res1, res2); } 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)); } 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; }