제출 #485042

#제출 시각아이디문제언어결과실행 시간메모리
485042maroonrk던전 (IOI21_dungeons)C++17
89 / 100
7101 ms1885104 KiB
#include "dungeons.h" #include <vector> #ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class t,class u> void print(const pair<t,u>&p,int suc=1){ print(p.a,2); print(p.b,suc); } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){ rep(i,v.size()) print(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print(const array<T,N>&v,int suc=1){ rep(i,N) print(v[i],i==int(N)-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } //N() が単位元 //VERIFY: yosupo //CF407E template<class N> struct segtree{ vc<N> x; int s; segtree(){} template<class t> segtree(vc<t> a){ int n=a.size(); s=1; while(s<n){s*=2;} x.resize(s*2); rep(i,n) x[s+i]=N(a[i]); gnr(i,1,s) x[i]=N::merge(x[i*2],x[i*2+1]); } //NOT Verified segtree(int n){ resize(n); } void resize(int n){ s=1; while(s<n){s*=2;} x.assign(s*2,N()); gnr(i,1,s) x[i]=N::merge(x[i*2],x[i*2+1]); } void set(int i,const N&t){ i+=s; x[i]=t; while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]); } N composite(int b,int e){ assert(b<=e); N lf,rt; for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){ if (l&1){ lf=N::merge(lf,x[l]); l++; } if (r&1){ r--; rt=N::merge(x[r],rt); } } return N::merge(lf,rt); } N getall(){ return x[1]; } //UTPC2020E //n 超えるかもしれない template <class F,class... Args> pair<int,N> max_right(int l,F f,Args&&... args){ assert(0<=l&&l<=s); if(l==s)return mp(s,N()); l+=s; N sm; assert((sm.*f)(forward<Args>(args)...)); do { while (l % 2 == 0) l >>= 1; if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){ while (l < s) { l = (2 * l); N tmp=N::merge(sm,x[l]); if ((tmp.*f)(forward<Args>(args)...)) { sm = tmp; l++; } } return mp(l - s,sm); } sm = N::merge(sm, x[l]); l++; } while ((l & -l) != l); return mp(s,sm); } //UTPC2020E template <class F,class... Args> pair<int,N> min_left(int r,F f,Args&&... args){ assert((N().*f)(forward<Args>(args)...)); assert(0<=r&&r<=s); if(r==0)return mp(0,N()); r+=s; N sm; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) { while (r < s) { r = (2 * r + 1); N tmp=N::merge(x[r],sm); if ((tmp.*f)(forward<Args>(args)...)) { sm = tmp; r--; } } return mp(r + 1 - s,sm); } sm = N::merge(x[r], sm); } while ((r & -r) != r); return mp(0,sm); } }; struct N{ int sum,mn; N(pi v=pi(0,inf)):sum(v.a),mn(v.b){} static N merge(const N&a,const N&b){ return N(pi(a.sum+b.sum,min(a.mn-b.sum,b.mn))); } bool ok(int v){ return mn>v; } }; const int L=26; struct Solver{ int n,ord; vvc<int> t; vi sub,par,in,head,jp,ni; vc<pi> ls; vc<N> acc; segtree<N> seg; void ae(int v,int p){ t[p].pb(v); sub[p]+=sub[v]; assert(par[v]==-1); par[v]=p; } void dfs(int v,int h,N w){ in[v]=ord++; head[v]=h; acc[v]=N::merge(w,acc[v]); for(auto&to:t[v]){ if(sub[to]>sub[t[v][0]]) swap(to,t[v][0]); } for(auto to:t[v]){ dfs(to,to==t[v][0]?h:to,to==t[v][0]?acc[v]:N(pi(0,inf))); } } void init(int nn,vi to,vi add,vi need,vc<pi> lls){ n=nn; ord=0; add.pb(0); need.pb(0); t.resize(n+1); sub.resize(n+1,1); par.resize(n+1,-1); in.resize(n+1,-1); head.resize(n+1,-1); jp.resize(n+1,-1); ni.resize(n+1,-1); ls=lls; ls.eb(0,-1); acc.resize(n+1); { vi cnt(n+1); rep(i,n)cnt[to[i]]++; vi qbuf;qbuf.reserve(n+1); rep(i,n+1)if(cnt[i]==0)qbuf.pb(i); rep(idx,si(qbuf)){ int v=qbuf[idx]; if(v<n){ int p=to[v]; ae(v,p); if(--cnt[p]==0)qbuf.pb(p); } } rep(i,n)if(cnt[i]){ int x=i; while(1){ assert(cnt[x]==1); cnt[x]=0; int y=to[x]; if(y!=i){ ae(x,y); x=y; }else{ jp[x]=y; break; } } } } rep(i,n+1)acc[i]=N(pi(add[i],need[i])); rep(r,n+1)if(par[r]==-1)dfs(r,r,N(pi(0,inf))); vc<pi> rw(n+1); rep(i,n+1){ ni[in[i]]=i; rw[in[i]]=pi(add[i],need[i]); } seg=segtree<N>(rw); } pi work(int x,int z){ assert(acc[x].mn<=z); auto [i,w]=seg.min_left(in[x]+1,&N::ok,z); z+=w.sum; x=ni[i-1]; z+=ls[x].a; x=ls[x].b; return pi(x,z); } pi slv(int x,int z){ while(1){ if(acc[x].mn<=z)return work(x,z); int h=head[x]; z+=acc[x].sum; if(par[h]==-1){ x=jp[h]; break; }else{ x=par[h]; } } dmp(par); dmp(jp); N cur(pi(0,inf)); while(1){ dmp(x); cur=N::merge(acc[x],cur); int h=head[x]; if(par[h]==-1){ x=jp[h]; break; }else{ x=par[h]; } } if(cur.mn>=z){ z+=(cur.mn-z+cur.sum-1)/cur.sum*cur.sum; } while(1){ dmp(x); if(acc[x].mn<=z)return work(x,z); int h=head[x]; z+=acc[x].sum; assert(par[h]!=-1); x=par[h]; } } } ss[L]; void init(signed n, std::vector<signed> s, std::vector<signed> p, std::vector<signed> w, std::vector<signed> l) { rep(lv,L){ vi to(n),add(n),need(n,inf); vc<pi> ls(n); rep(i,n){ if(s[i]<=mask(lv)){ to[i]=w[i]; add[i]=s[i]; }else{ to[i]=l[i]; add[i]=p[i]; need[i]=s[i]; } ls[i]=pi(s[i],w[i]); } ss[lv].init(n,to,add,need,ls); } } long long simulate(signed x,signed z_){ int z=z_; while(x!=-1){ dmp2(x,z); int lv=min(topbit(z),L-1); tie(x,z)=ss[lv].slv(x,z); } return z; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...