제출 #485001

#제출 시각아이디문제언어결과실행 시간메모리
485001maroonrk던전 (IOI21_dungeons)C++17
0 / 100
2 ms972 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); } #ifdef LOCAL const int nmax=1000; const int B=50; #else const int nmax=400000; const int B=1000; #endif const ll L=40; const ll M=mask(L); struct N{ ll sum; int mn; }; N* buf[nmax/B]; //sum に変な情報をもたせていない void mg(N&a,const N&b){ if(b.mn!=inf) chmin(a.mn,max(b.mn-a.sum,0LL)); a.sum+=b.sum; } vi ls; int n,to[nmax+1],gain[nmax+1],cap[nmax+1],dep[nmax+1]; void load2buf(int tar){ static int cnt[nmax+1],qbuf[nmax+1]; rep(i,n+1)cnt[i]=0; rep(i,n+1)if(to[i]!=-1)cnt[to[i]]++; int head=0; rep(i,n+1)if(cnt[i]==0)qbuf[head++]=i; rep(i,head){ int v=qbuf[i]; if(to[v]!=-1&&--cnt[to[v]]==0) qbuf[head++]=to[v]; } rep(i,n+1)if(cnt[i]){ int x=i,last=-1; do{ assert(cnt[x]==1); cnt[x]=0; qbuf[head++]=x; last=x; x=to[x]; }while(x!=i); to[last]=-1; } per(i,n+1){ int v=qbuf[i]; if(to[v]!=-1&&dep[to[v]]==B-1)to[v]=-1; if(to[v]==-1){ buf[tar][v]={ll(v)<<L,inf}; dep[v]=0; }else{ buf[tar][v].sum=buf[tar][to[v]].sum+gain[v]; int w=buf[tar][to[v]].mn; buf[tar][v].mn=min(cap[v],w==inf?inf:max(w-gain[v],0)); dep[v]=dep[to[v]]+1; } } } int addup[nmax],addlw[nmax],goup[nmax],golw[nmax]; void init(int n_, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { N*ptr=new N[(n+1)*(nmax/B)]; rep(i,nmax/B)buf[i]=ptr+i*(n+1); ls=s;mkuni(ls); n=n_; for(int i=0;i<si(ls);i+=B){ int j=min(i+B,si(ls)); int lw=ls[i],up=ls[j-1]; rep(k,n){ if(inc(lw,s[k],up))to[k]=-1; else if(s[k]<lw){ to[k]=l[k]; gain[k]=p[k]; cap[k]=s[k]; }else{ to[k]=w[k]; gain[k]=s[k]; cap[k]=inf; } } to[n]=-1; load2buf(i/B); i=j; } rep(i,n){ addup[i]=s[i]; addlw[i]=p[i]; goup[i]=w[i]; golw[i]=l[i]; } } int lastvis[nmax],pos[nmax],idx[nmax]; N work[nmax]; int curtime; long long simulate(int x,int z_){ ll z=z_; while(x!=n){ curtime++; int tar=lower_bound(all(ls),z)-ls.bg; if(tar==si(ls))tar--; tar/=B; ll ini=z; auto advance=[&](){ while(1){ if(addup[x]<=ini){ z+=addup[x]; x=goup[x]; }else if(z<addup[x]){ z+=addlw[x]; x=golw[x]; }else{ z+=addup[x]; x=goup[x]; break; } } }; int s=0; while(x!=n){ if(lastvis[x]==curtime){ int p=pos[x]; N cur={0,inf}; rng(i,p,s)mg(cur,work[i]); if(cur.mn>z){ z+=(cur.mn-z+cur.sum-1)/cur.sum*cur.sum; } bool did=false; rng(i,p,s){ if(work[i].mn>z){ z+=work[i].sum; }else{ x=idx[i]; advance(); did=true; break; } } assert(did); break; }else{ lastvis[x]=curtime; pos[x]=s++; idx[s-1]=x; work[s-1]=buf[tar][x]; int y=buf[tar][x].sum>>L; work[s-1].sum&=M; if(y<n){ mg(work[s-1],addup[y]<=ini?N{addup[y],inf}:N{addlw[y],addup[y]}); y=addup[y]<=ini?goup[y]:golw[y]; } if(work[s-1].mn<=z){ advance(); break; } z+=work[s-1].sum; x=y; } } } 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...