結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | Tqk |
提出日時 | 2019-11-25 15:16:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,495 bytes |
コンパイル時間 | 4,410 ms |
コンパイル使用メモリ | 231,844 KB |
実行使用メモリ | 29,352 KB |
最終ジャッジ日時 | 2024-10-13 08:17:55 |
合計ジャッジ時間 | 17,327 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 4 ms
5,248 KB |
testcase_04 | AC | 4 ms
5,248 KB |
testcase_05 | AC | 4 ms
5,248 KB |
testcase_06 | AC | 4 ms
5,248 KB |
testcase_07 | AC | 379 ms
29,320 KB |
testcase_08 | AC | 377 ms
29,316 KB |
testcase_09 | AC | 380 ms
29,316 KB |
testcase_10 | AC | 381 ms
29,316 KB |
testcase_11 | AC | 396 ms
29,316 KB |
testcase_12 | AC | 365 ms
29,324 KB |
testcase_13 | AC | 373 ms
29,320 KB |
testcase_14 | AC | 363 ms
29,324 KB |
testcase_15 | AC | 361 ms
29,316 KB |
testcase_16 | AC | 370 ms
29,316 KB |
testcase_17 | AC | 389 ms
29,240 KB |
testcase_18 | AC | 400 ms
29,316 KB |
testcase_19 | AC | 391 ms
29,312 KB |
testcase_20 | AC | 397 ms
29,316 KB |
testcase_21 | AC | 397 ms
29,320 KB |
testcase_22 | AC | 313 ms
29,352 KB |
testcase_23 | AC | 322 ms
29,316 KB |
testcase_24 | AC | 331 ms
29,320 KB |
testcase_25 | AC | 331 ms
29,320 KB |
testcase_26 | AC | 339 ms
29,188 KB |
testcase_27 | AC | 307 ms
29,324 KB |
testcase_28 | AC | 306 ms
29,316 KB |
testcase_29 | AC | 307 ms
29,316 KB |
コンパイルメッセージ
main.cpp:211:8: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 211 | mint<> operator""m(const unsigned long long n){ return mint<>(n); } | ^~~~~~~~ main.cpp:212:17: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 212 | mint<998244353> operator""m9(const unsigned long long n){ return mint<998244353>(n); } | ^~~~~~~~ main.cpp:213:15: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 213 | mint<1000003> operator""m3(const unsigned long long n){ return mint<1000003>(n); } | ^~~~~~~~
ソースコード
//sub-BOF //#define _AOJ_ /*vvv> zzzzzI .---. zzuzuI .vgggg&,. +++++= dAC:|I .WbbWo JMM9^```?TMB` ..&gNNg,. gggggggJ, qgggggggg] (&&&&&&&&[ c+OA&J, (&&&&&&+J, .cJeAA&-. (&&&&&&&&x .&AA&=-. +++++= dTqk|I Xpbpbp JM#` (M#^ ?MMp MM| +TMN. JMF ' |yk ` dVY 7Vk, Vy XV cVf ?Y! JM V$ ` +++++= dcf:|I Xppppp dMN .MM+ .MM MM| MM] JMMMMMM+ |@tqkoh) ,y0 (V$ yyyyyyyV7 VV JMWyZWr TWVVVVW&, ++++++ d7qk|0 Xppppp ^HMN, _.db WMm, .MMF MM| ..MM` JMF . |yk .WV&. .XW' yy 4yn. jyn +. JM #S `++++` ?ZZZX= ?WWWW= -THMMMMH9^ (TMMMMM9! MMMMMMM"" JMMMMMMMME |UU. ?TUUUUY= UU. (UU- ^7TUUUV7! JUUUUUUUU 7TUNKO*/ #pragma region template #pragma region basic #pragma GCC optimize ("O3")//#pragma GCC optimize ("fast-math") #pragma GCC target ("avx2") #include "bits/stdc++.h" using namespace std; typedef long long lint; typedef long double ld; typedef string cs; #pragma endregion #pragma region rep #define _vcppunko4(tuple) _getname4 tuple #define _getname4(_1,_2,_3,_4,name,...) name #define _getname3(_1,_2,_3,name,...) name #define _trep2(tuple) _rep2 tuple #define _trep3(tuple) _rep3 tuple #define _trep4(tuple) _rep4 tuple #define _rep1(n) for(lint i=0;i<n;++i) #define _rep2(i,n) for(lint i=0;i<n;++i) #define _rep3(i,a,b) for(lint i=a;i<b;++i) #define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c) #define _trrep2(tuple) _rrep2 tuple #define _trrep3(tuple) _rrep3 tuple #define _trrep4(tuple) _rrep4 tuple #define _rrep1(n) for(lint i=n-1;i>=0;--i) #define _rrep2(i,n) for(lint i=n-1;i>=0;--i) #define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i) #define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c) #define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__)) #define per(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__)) #define each(c) for(auto &e:c) #pragma endregion #pragma region io template<class T> istream& operator>>(istream& is,vector<T>& vec); template<class T,size_t size> istream& operator>>(istream& is,array<T,size>& vec); template<class T,class L> istream& operator>>(istream& is,pair<T,L>& p); template<class T> ostream& operator<<(ostream& os,vector<T>& vec); template<class T,class L> ostream& operator<<(ostream& os,pair<T,L>& p); template<class T> istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; } template<class T,class L> istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; } template<class T,class L> ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; } template<class T> ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; } template<class T> ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; } #ifdef __ENV_TQK__ #include<Windows.h> HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); inline void in(){ SetConsoleTextAttribute(hConsole,10); } template <class Head,class... Tail> inline void in(Head&& head,Tail&&... tail){ SetConsoleTextAttribute(hConsole,15); cin>>head;in(move(tail)...); } #else inline void in(){} template <class Head,class... Tail> inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); } #endif inline bool out(){ return(cout<<'\n',0); } template <class T> inline bool out(T t){ return(cout<<t<<'\n',0); } template <class Head,class... Tail> inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; } template <class T> inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); } #define alc alloc #pragma endregion #pragma region TA #define lin(...) lint __VA_ARGS__;in(__VA_ARGS__) #define stin(...) string __VA_ARGS__;in(__VA_ARGS__) #define vin(type,name,size) vector<type> name(size);in(name) #define vvin(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name) #define all(v) v.begin(),v.end() #define pb push_back #define fi e.first #define se e.second #define YES(c) cout<<((c)?"YES\n":"NO\n"),0 #define Yes(c) cout<<((c)?"Yes\n":"No\n"),0 #define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0 #define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0 #define o(p) cout<<p<<endl,0 #define sp(p) cout<<p<<" ",0 #define no(p) cout<<p,0 #define psort(l,r) if(l>r)swap(l,r); inline constexpr lint gcd(lint a,lint b){ if(!a||!b)return 0;while(b){ lint c=b;b=a%b;a=c; }return a; } template<typename T> inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; } template<typename T> inline constexpr bool chmax(T &mx,const T &cnt){ if(mx<cnt){ mx=cnt;return 1; } else return 0; } #define ve(type) vector<type> #define fn(ty1,ty2,ex) [](ty1 a,ty2 b){ return(ex); } #define lfn(ex) [](lint a,lint b){ return(ex); } #pragma endregion #pragma region other #ifdef __ENV_TQK__ #define deb(...) out(__VA_ARGS__) #define dsp(ex) sp(ex) #define dno(ex) no(ex) #else #define deb(...) 0 #define dsp(ex) 0 #define dno(ex) 0 #endif struct Fastio{ Fastio(){ cin.tie(0),cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(10); } } __fastio; #pragma endregion #pragma region mint #define md_tmp template<uint_fast64_t md=1000000007> md_tmp class mint{ using u64=uint_fast64_t; public: u64 a; constexpr mint(const u64 x=0) noexcept: a(x%md){} constexpr u64 &value() noexcept{ return a; } constexpr const u64 &value() const noexcept{ return a; } constexpr mint operator+(const mint rhs) const noexcept{ return mint(*this)+=rhs; } constexpr mint operator-(const mint rhs) const noexcept{ return mint(*this)-=rhs; } constexpr mint operator*(const mint rhs) const noexcept{ return mint(*this)*=rhs; } constexpr mint operator^(const lint rhs) const noexcept{ return mint(*this)^=rhs; } constexpr mint operator/(const mint rhs) const noexcept{ return mint(*this)/=rhs; } constexpr mint &operator+=(const mint rhs) noexcept{ a+=rhs.a; if(a>=md)a-=md; return *this; } constexpr mint &operator-=(const mint rhs) noexcept{ if(a<rhs.a)a+=md; a-=rhs.a; return *this; } constexpr mint &operator*=(const mint rhs) noexcept{ a=a*rhs.a%md; return *this; } constexpr mint &operator^=(const lint rhs) noexcept{ if(!rhs)return *this=1; u64 exp=rhs-1; mint base=this->a; while(exp){ if(exp&1)*this*=base; base*=base; exp>>=1; } return *this; } constexpr mint &operator/=(const mint rhs) noexcept{ a=(*this*(rhs^(md-2))).a; return *this; } }; md_tmp istream& operator>>(istream& os,mint<md>& m){ os>>m.a,m.a%=md; return os; } md_tmp ostream& operator<<(ostream& os,const mint<md>& m){ return os<<m.a; } md_tmp mint<md> ncr(lint n,lint r){ if(n<r||n<0||r<0)return mint<md>(0); mint<md>ncr_res=1,ncr_div=1; rep(r)ncr_res*=(n-i),ncr_div*=(r-i); return ncr_res/ncr_div; } #ifndef _AOJ_ mint<> operator""m(const unsigned long long n){ return mint<>(n); } mint<998244353> operator""m9(const unsigned long long n){ return mint<998244353>(n); } mint<1000003> operator""m3(const unsigned long long n){ return mint<1000003>(n); } #endif #pragma endregion #pragma region P class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; }; istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; } constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); } constexpr bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); } constexpr bool operator<=(const P& l,const P& r){ return!(l.f-r.f?l.f>r.f:l.s>r.s); } constexpr bool operator>=(const P& l,const P& r){ return!(l.f-r.f?l.f<r.f:l.s<r.s); } #pragma endregion #pragma region rec_lambda template<typename F> #if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) [[nodiscard]] #elif defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4) __attribute__((warn_unused_result)) #endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) static inline constexpr decltype(auto) rec(F&& f) noexcept{ return[f = std::forward<F>(f)](auto&&... args) { return f(f,std::forward<decltype(args)>(args)...); }; } #pragma endregion #pragma endregion #pragma region const #define linf 1152921504606846976 //#define inf linf #define MAXN 101010 #define md_1e9_7 1000000007 #define md_998244353 998244353 #define pi 3.14159265358979323846 //#define mod md_1e9_7 const int d4[5]={0,1,0,-1,0}; #pragma endregion using length=lint;//info an edge has struct edge{ int src,to; length cost; edge(){} edge(int to,length cost): src(-1),to(to),cost(cost){} edge(int src,int to,length cost): src(src),to(to),cost(cost){} edge &operator=(const int &x){ to=x; return *this; } operator int() const{ return to; } }; istream& operator>>(istream& os,edge& e){ os>>e.src>>e.to>>e.cost;return os; } using Matrix=vector<vector<length> >; using Edges=vector<edge>; using Weighted=vector<Edges>; using UnWeighted=vector<vector<int> >; // HLD( <tree> , root ) // === .build() === // .fold(hi, lo, func, inclusive) // where func(l, r) proceeds with [l, r) // === O(1) === // .in(a) : in-time of Euler Tour : alias = .[a] // .out(a) : out-time of Euler Tour // .rev(a) : rev[in[a]] = a // .head(a) : ascend all light edges // .tail(a) : descend all heavy edges // --- // .subtree_size(a) // .depth(a) : 0-indexed // .parent(a) : -1 if [a] is root // .heavy(a) : [a] cannot be a leaf. return the node opposite of the heavy edge // === O(log n) === // .climb(a) // .descendTo(from, to, steps) // .steps(a, b) // === --- === // for subtree : [ .in(a) , .out(a) ) // (exclusive) : [ .in_exclusive(a) , .out(a) ) // HL-Decomposition {{{ // based on Euler Tour struct HLD{ public: using size_type = std::size_t; using graph_type = std::vector< std::vector< int > >; private: size_type n; std::vector< size_type > hd,tl; std::vector< size_type > sub; std::vector< size_type > dep; std::vector< int > par; std::vector< size_type > vid; size_type root; graph_type tree; public: HLD(): n(0){} HLD(size_type n,size_type root = 0) : n(n),hd(n),tl(n),sub(n),dep(n),par(n),vid(n),tree(n){ setRoot(root); } HLD(const graph_type &tree,size_type root): HLD(tree.size(),root){ this->tree = tree; } void setRoot(size_type root){ assert(root < n); this->root = root; } private: bool built = 0; std::vector< size_type > vid_rev; public: void build(){ assert(!built && n); built = 1; vid_rev.resize(n); hd[root] = root; dfs0(); dfs1(); for(size_type i = 0; i < n; i++) vid_rev[vid[i]] = i; } private: void dfs0(){ std::vector< int > used(n); std::vector< std::tuple< size_type,int,size_type > > stk; stk.reserve(n); stk.emplace_back(root,-1,0); while(stk.size()){ size_type i,d; int p; std::tie(i,p,d) = stk.back(); if(!used[i]){ used[i] = 1; par[i] = p; dep[i] = d; for(auto &j : tree[i]) if(j != p){ stk.emplace_back(j,i,d + 1); } } else{ stk.pop_back(); sub[i] = 1; for(auto &j : tree[i]) if(j != p){ if(sub[j] > sub[tree[i].back()]){ std::swap(tree[i].back(),j); } sub[i] += sub[j]; } if(tree[i].back() != p){ tl[i] = tl[tree[i].back()]; } else{ tl[i] = i; } } } } void dfs1(){ std::vector< int > used(n); std::vector< std::tuple< size_type,int > > stk; stk.reserve(n); stk.emplace_back(root,-1); size_type id = 0; while(stk.size()){ size_type i; int p; std::tie(i,p) = stk.back(),stk.pop_back(); vid[i] = id++; for(auto j : tree[i]) if(j != p){ hd[j] = j == tree[i].back() ? hd[i] : j; stk.emplace_back(j,i); } } } public: size_type operator[](size_type i) const{ return in(i); } size_type in(size_type i) const{ assert(built); assert(i < n); return vid[i]; } size_type in_exclusive(size_type i) const{ return in(i) + 1; } size_type out(size_type i) const{ assert(built); assert(i < n); return vid[i] + sub[i]; } size_type out_exclusive(size_type i) const{ return out(i) - 1; } size_type head(size_type i) const{ assert(built); return hd.at(i); } size_type tail(size_type i) const{ assert(built); return tl.at(i); } size_type rev(size_type i) const{ assert(built); return vid_rev.at(i); } size_type subtree_size(size_type i) const{ assert(built); return sub.at(i); } size_type depth(size_type i) const{ assert(built); return dep.at(i); } int parent(size_type i) const{ assert(built); return par.at(i); } size_type steps(size_type a,size_type b) const{ assert(built); assert(a < n && b < n); return dep[a] + dep[b] - 2 * dep[lca(a,b)]; } size_type climb(size_type a,long long t) const{ assert(built); assert(a < n && t >= 0); while(t){ long long c = std::min< long long >(vid[a] - vid[hd[a]],t); t -= c; a = vid_rev[vid[a] - c]; if(t && a != root){ t--; a = par[a]; } if(a == root) break; } return a; } size_type descendTo(size_type from,size_type to,long long steps) const{ assert(built); assert(steps >= 0); assert(from < n && to < n); return climb(to,dep[to] - dep[from] - steps); } void add_edge(size_type a,size_type b){ assert(built); assert(a < n && b < n); tree[a].emplace_back(b); tree[b].emplace_back(a); } size_type lca(size_type a,size_type b) const{ assert(built); assert(a < n && b < n); while(1){ if(vid[a] > vid[b]) std::swap(a,b); if(hd[a] == hd[b]) return a; b = par[hd[b]]; } } size_type heavy(size_type a) const{ assert(built); assert(a < n); assert(tree[a].back() != par[a]); return tree[a].back(); } void _fold_vertex(size_type hi,int lo,std::function< void(int,int) > f, bool inclusive) const{ assert(built); assert(hi < n && 0 <= lo && lo < (int)n); while(lo != -1 && dep[lo] >= dep[hi]){ size_type nex = max(vid[hd[lo]],vid[hi]); f(nex + (nex == vid[hi] && !inclusive),vid[lo] + 1); lo = par[hd[lo]]; } } void _fold_edge(size_type hi,int lo,std::function< void(int,int) > f) const{ assert(built); assert(hi < n && 0 <= lo && lo < (int)n); while(lo != -1 && dep[lo] >= dep[hi]){ size_type nex = max(vid[hd[lo]],vid[hi]); f(nex+(nex==vid[hi]),vid[lo]+1); lo = par[hd[lo]]; } } void fold_path_vertex(int s,int t,std::function< void(int,int) > f) const{ int l=lca(s,t); _fold_vertex(l,s,f,1); _fold_vertex(l,t,f,0); } void fold_path_edge(int s,int t,std::function< void(int,int) > f) const{ int l=lca(s,t); _fold_edge(l,s,f); _fold_edge(l,t,f); } void fold_subtree_vertex(int i,std::function< void(int,int) > f) const{ f(in(i),out(i)); } void fold_subtree_edge(int i,std::function< void(int,int) > f) const{ f(in(i)+1,out(i)); } size_type distance(size_type a,size_type b) const{ return depth(a)+depth(b)-2*depth(lca(a,b)); } size_type size() const{ return n; } }; // }}} class Ushi{ public: using T=lint; using func=function<T(T,T)>; int n,sz; vector<lint> node; func f; T e; Ushi(vector<T> v,func f,T e):f(f),e(e){ sz=v.size();n=1; while(n<sz)n<<=1; node.resize(2*n,e); rep(i,sz)node[n+i]=v[i]; for(int i=n-1;i>0;--i)node[i]=f(node[2*i],node[2*i+1]); } T* at(int i){ return &node[i+n]; }//use like *tree.at(i)=x,tree.adjust(i); void adjust(int i){ i+=n;while(i>>=1)node[i]=f(node[2*i],node[2*i+1]); } T fold(int a,int b,int k=1,int l=0,int r=-1){ if(r<0)r=n; if(r<=a||b<=l)return e; if(a<=l&&r<=b)return node[k]; return f(fold(a,b,2*k,l,(l+r)/2),fold(a,b,2*k+1,(l+r)/2,r)); } };//verified(DSL_2_A,DSL_2_B):http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3604788#1 int main(){ lint n,u,v,w;in(n); UnWeighted g(n); map<P,lint> _len; vector<lint>len(n);//after hld rep(n-1){ in(u,v,w); psort(u,v); g[u].pb(v),g[v].pb(u); _len[P(u,v)]=w; } HLD h(g,0);h.build(); rep(i,1,n){ int u=h.parent(i),v=i; psort(u,v); len[h.in(i)]=_len[P(u,v)]; } Ushi ki(len,[](lint a,lint b){return a+b;},0); //end-input lint q;in(q); while(q--){ int k,ans=0;in(k); vector<int>x(k);in(x); sort(all(x),[&](int l,int r){return h.in(l)<h.in(r);}); int lca=x[0]; rep(k-1){ int l=h.lca(x[i],x[i+1]); h.fold_path_edge(l,x[i+1],[&](int l,int r){ans+=ki.fold(l,r);}); if(h.depth(l)<h.depth(lca))lca=l; } h.fold_path_edge(lca,x[0],[&](int l,int r){ans+=ki.fold(l,r);}); out(ans); } } //sub-EOF