結果
問題 | No.2654 [Cherry 6th Tune] Re: start! (Black Sheep) |
ユーザー | Taiki0715 |
提出日時 | 2024-02-23 22:39:09 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 843 ms / 7,000 ms |
コード長 | 7,522 bytes |
コンパイル時間 | 5,108 ms |
コンパイル使用メモリ | 178,128 KB |
実行使用メモリ | 51,632 KB |
最終ジャッジ日時 | 2024-02-23 22:39:33 |
合計ジャッジ時間 | 21,906 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 3 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 442 ms
13,716 KB |
testcase_04 | AC | 420 ms
13,096 KB |
testcase_05 | AC | 233 ms
9,216 KB |
testcase_06 | AC | 70 ms
6,676 KB |
testcase_07 | AC | 201 ms
8,192 KB |
testcase_08 | AC | 269 ms
9,856 KB |
testcase_09 | AC | 454 ms
13,768 KB |
testcase_10 | AC | 67 ms
6,676 KB |
testcase_11 | AC | 321 ms
10,752 KB |
testcase_12 | AC | 57 ms
6,676 KB |
testcase_13 | AC | 299 ms
10,368 KB |
testcase_14 | AC | 605 ms
16,760 KB |
testcase_15 | AC | 530 ms
16,032 KB |
testcase_16 | AC | 267 ms
9,216 KB |
testcase_17 | AC | 459 ms
14,412 KB |
testcase_18 | AC | 185 ms
7,680 KB |
testcase_19 | AC | 563 ms
16,448 KB |
testcase_20 | AC | 275 ms
10,240 KB |
testcase_21 | AC | 305 ms
11,008 KB |
testcase_22 | AC | 314 ms
10,752 KB |
testcase_23 | AC | 2 ms
6,676 KB |
testcase_24 | AC | 3 ms
6,676 KB |
testcase_25 | AC | 3 ms
6,676 KB |
testcase_26 | AC | 3 ms
6,676 KB |
testcase_27 | AC | 4 ms
6,676 KB |
testcase_28 | AC | 646 ms
17,584 KB |
testcase_29 | AC | 661 ms
17,456 KB |
testcase_30 | AC | 689 ms
17,456 KB |
testcase_31 | AC | 625 ms
17,584 KB |
testcase_32 | AC | 589 ms
17,456 KB |
testcase_33 | AC | 843 ms
51,632 KB |
testcase_34 | AC | 330 ms
18,128 KB |
testcase_35 | AC | 411 ms
17,584 KB |
testcase_36 | AC | 399 ms
51,632 KB |
testcase_37 | AC | 493 ms
17,584 KB |
testcase_38 | AC | 458 ms
51,632 KB |
testcase_39 | AC | 1 ms
6,676 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL clock_t start=clock(); #endif int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } #ifdef LOCAL cerr<<"time:"; cerr<<(clock()-start)/1000; cerr<<"ms\n"; #endif } template<typename S,S(*op)(S,S),S(*e)()> struct splay_tree{ struct node{ node *par,*left,*right; int sz; S val,sum; node():par(nullptr),left(nullptr),right(nullptr),sz(1),val(e()),sum(e()){} void set(S v){ this->val=v; this->sum=v; if(this->left)this->sum=op(this->left->sum,this->sum); if(this->right)this->sum=op(this->sum,this->right->sum); } void rotate(){ node *pp,*p,*c; p=this->par; pp=p->par; if(p->left==this){ c=this->right; this->right=p; p->left=c; } else{ c=this->left; this->left=p; p->right=c; } if(pp&&pp->left==p)pp->left=this; if(pp&&pp->right==p)pp->right=this; this->par=pp; p->par=this; if(c)c->par=p; p->update(); this->update(); } int state()const{ if(!this->par)return 0; if(this->par->left==this)return 1; if(this->par->right==this)return -1; return 0; } void splay(){ while(this->state()){ if(this->par->state()==0)this->rotate(); else if(this->state()==this->par->state()){ this->par->rotate(); this->rotate(); } else{ this->rotate(); this->rotate(); } } } void update(){ this->sz=1; this->sum=this->val; if(this->left){ this->sz+=this->left->sz; this->sum=op(this->left->sum,this->sum); } if(this->right){ this->sz+=this->right->sz; this->sum=op(this->sum,this->right->sum); } } }; private: node *root=nullptr; node *get(int id,node *root){ node *now=root; while(true){ int lsize=now->left?now->left->sz:0; if(id<lsize)now=now->left; else if(id==lsize){ now->splay(); return now; } else{ now=now->right; id-=lsize+1; } } } node *merge(node *lroot,node *rroot){ if(!lroot)return rroot; if(!rroot)return lroot; lroot=get(lroot->sz-1,lroot); lroot->right=rroot; rroot->par=lroot; lroot->update(); return lroot; } pair<node*,node*>split(int lcnt,node *root){ if(lcnt==0)return {nullptr,root}; if(lcnt==root->sz)return {root,nullptr}; root=get(lcnt,root); node *lroot,*rroot; lroot=root->left; rroot=root; lroot->par=nullptr; rroot->left=nullptr; rroot->update(); return {lroot,rroot}; } node *insert(int id,node *nd,node *root){ auto spl=split(id,root); return merge(merge(spl.first,nd),spl.second); } node *erase(int id,node *root){ root=get(id,root); node *lroot=root->left; node *rroot=root->right; if(lroot)lroot->par=nullptr; if(rroot)rroot->par=nullptr; delete(root); return merge(lroot,rroot); } node *between(int l,int r){ if(l==0&&r==this->root->sz)return this->root; if(l==0){ root=get(r,root); return root->left; } if(r==this->root->sz){ root=get(l-1,root); return root->right; } node *rht=get(r,root); node *lft=rht->left; lft->par=nullptr; root=lft; lft=get(l-1,lft); root=rht; rht->left=lft; lft->par=rht; rht->update(); return lft->right; } public: const S &operator[](int id){ root=get(id,root); return root->val; } void insert(S x){ node *nd=new node(); nd->set(x); if(!root){ root=insert(0,nd,root); return; } node *now=root; while(true){ if(now->val==x){ now->splay(); root=now; int lsize=root->left?root->left->sz:0; root=insert(lsize,nd,root); return; } else if(now->val>x){ if(!now->left){ now->left=nd; nd->par=now; nd->splay(); root=nd; return; } else now=now->left; } else{ if(!now->right){ now->right=nd; nd->par=now; nd->splay(); root=nd; return; } else now=now->right; } } } void erase(S x){ if(!root)return; node *now=root; while(true){ if(now->val==x){ now->splay(); root=now; int lsize=now->left?now->left->sz:0; root=erase(lsize,root); return; } else if(now->val>x){ if(!now->left)return; else now=now->left; } else{ if(!now->right)return; else now=now->right; } } } int size()const{return root?root->sz:0;} S prod(int l,int r){ if(l==r)return e(); node *pr=between(l,r); return pr->sum; } }; using S=ll; S op(S x, S y){return x+y;} S e(){return 0;} void SOLVE(){ int n; cin>>n; n++; vector<ll>a(n); cin>>a; splay_tree<S,op,e>seg; vector<vector<int>>to(n); rep(i,n-1){ int u,v; cin>>u>>v; to[u].push_back(v); to[v].push_back(u); } vector<ll>ans(n,-1); auto dfs=[&](auto self,int x,int p)->void { seg.insert(a[x]); int sz=seg.size(); if(sz>=3){ if(seg[0]==seg[sz-1]){ ans[x]=1; } else{ ans[x]=1e18; chmin(ans[x],seg.prod(sz/2+1,sz)-seg.prod(1,(sz+1)/2)); chmin(ans[x],seg.prod(sz/2,sz-1)-seg.prod(0,(sz+1)/2-1)); } } for(auto i:to[x])if(i!=p){ self(self,i,x); } seg.erase(a[x]); }; dfs(dfs,0,-1); reps(i,1,n)cout<<ans[i]<<endl; }