Submission #485048

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485048	2021-11-06T00:26:49 Z	maroonrk	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6833 ms	1829168 KB

dungeons

#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;
	vc<pi> es;
	vi deg;
	void ae(int v,int p){
		//t[p].pb(v);
		es.eb(v,p);
		deg[p]++;
		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);
		es.reserve(n);
		deg.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)t[i].resize(deg[i]);
		for(auto [v,p]:es)t[p][--deg[p]]=v;
		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);
		
		vi().swap(sub);
		vc<pi>().swap(es);
		vi().swap(deg);
	}
	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){
		int lv=min(topbit(z),L-1);
		tie(x,z)=ss[lv].slv(x,z);
	}
	return z;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	10 ms	8292 KB	Output is correct
4	Correct	331 ms	209012 KB	Output is correct
5	Correct	10 ms	8268 KB	Output is correct
6	Correct	327 ms	208900 KB	Output is correct

Subtask #2

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4300 KB	Output is correct
2	Correct	2854 ms	1729856 KB	Output is correct
3	Correct	2698 ms	1813688 KB	Output is correct
4	Correct	3268 ms	1780172 KB	Output is correct
5	Correct	4799 ms	1666960 KB	Output is correct
6	Correct	2911 ms	1736664 KB	Output is correct
7	Correct	2357 ms	1814732 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4300 KB	Output is correct
2	Correct	374 ms	210488 KB	Output is correct
3	Correct	363 ms	210808 KB	Output is correct
4	Correct	310 ms	227068 KB	Output is correct
5	Correct	316 ms	217048 KB	Output is correct
6	Correct	378 ms	210560 KB	Output is correct
7	Correct	379 ms	210684 KB	Output is correct
8	Correct	316 ms	226340 KB	Output is correct
9	Correct	366 ms	208556 KB	Output is correct
10	Correct	311 ms	227844 KB	Output is correct
11	Correct	388 ms	227804 KB	Output is correct
12	Correct	409 ms	228208 KB	Output is correct
13	Correct	311 ms	227068 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4300 KB	Output is correct
2	Correct	374 ms	210488 KB	Output is correct
3	Correct	363 ms	210808 KB	Output is correct
4	Correct	310 ms	227068 KB	Output is correct
5	Correct	316 ms	217048 KB	Output is correct
6	Correct	378 ms	210560 KB	Output is correct
7	Correct	379 ms	210684 KB	Output is correct
8	Correct	316 ms	226340 KB	Output is correct
9	Correct	366 ms	208556 KB	Output is correct
10	Correct	311 ms	227844 KB	Output is correct
11	Correct	388 ms	227804 KB	Output is correct
12	Correct	409 ms	228208 KB	Output is correct
13	Correct	311 ms	227068 KB	Output is correct
14	Correct	5 ms	4300 KB	Output is correct
15	Correct	348 ms	209296 KB	Output is correct
16	Correct	379 ms	210700 KB	Output is correct
17	Correct	325 ms	213476 KB	Output is correct
18	Correct	331 ms	213484 KB	Output is correct
19	Correct	400 ms	210904 KB	Output is correct
20	Correct	347 ms	216072 KB	Output is correct
21	Correct	344 ms	215304 KB	Output is correct
22	Correct	327 ms	216176 KB	Output is correct
23	Correct	384 ms	225656 KB	Output is correct
24	Correct	400 ms	225512 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4300 KB	Output is correct
2	Correct	374 ms	210488 KB	Output is correct
3	Correct	363 ms	210808 KB	Output is correct
4	Correct	310 ms	227068 KB	Output is correct
5	Correct	316 ms	217048 KB	Output is correct
6	Correct	378 ms	210560 KB	Output is correct
7	Correct	379 ms	210684 KB	Output is correct
8	Correct	316 ms	226340 KB	Output is correct
9	Correct	366 ms	208556 KB	Output is correct
10	Correct	311 ms	227844 KB	Output is correct
11	Correct	388 ms	227804 KB	Output is correct
12	Correct	409 ms	228208 KB	Output is correct
13	Correct	311 ms	227068 KB	Output is correct
14	Correct	5 ms	4300 KB	Output is correct
15	Correct	348 ms	209296 KB	Output is correct
16	Correct	379 ms	210700 KB	Output is correct
17	Correct	325 ms	213476 KB	Output is correct
18	Correct	331 ms	213484 KB	Output is correct
19	Correct	400 ms	210904 KB	Output is correct
20	Correct	347 ms	216072 KB	Output is correct
21	Correct	344 ms	215304 KB	Output is correct
22	Correct	327 ms	216176 KB	Output is correct
23	Correct	384 ms	225656 KB	Output is correct
24	Correct	400 ms	225512 KB	Output is correct
25	Correct	330 ms	209928 KB	Output is correct
26	Correct	394 ms	210816 KB	Output is correct
27	Correct	339 ms	208644 KB	Output is correct
28	Correct	340 ms	208664 KB	Output is correct
29	Correct	398 ms	210752 KB	Output is correct
30	Correct	333 ms	226952 KB	Output is correct
31	Correct	341 ms	226940 KB	Output is correct
32	Correct	400 ms	225528 KB	Output is correct
33	Correct	429 ms	227836 KB	Output is correct
34	Correct	711 ms	225316 KB	Output is correct
35	Correct	450 ms	223340 KB	Output is correct

Subtask #6

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4300 KB	Output is correct
2	Correct	2854 ms	1729856 KB	Output is correct
3	Correct	2698 ms	1813688 KB	Output is correct
4	Correct	3268 ms	1780172 KB	Output is correct
5	Correct	4799 ms	1666960 KB	Output is correct
6	Correct	2911 ms	1736664 KB	Output is correct
7	Correct	2357 ms	1814732 KB	Output is correct
8	Correct	5 ms	4300 KB	Output is correct
9	Correct	374 ms	210488 KB	Output is correct
10	Correct	363 ms	210808 KB	Output is correct
11	Correct	310 ms	227068 KB	Output is correct
12	Correct	316 ms	217048 KB	Output is correct
13	Correct	378 ms	210560 KB	Output is correct
14	Correct	379 ms	210684 KB	Output is correct
15	Correct	316 ms	226340 KB	Output is correct
16	Correct	366 ms	208556 KB	Output is correct
17	Correct	311 ms	227844 KB	Output is correct
18	Correct	388 ms	227804 KB	Output is correct
19	Correct	409 ms	228208 KB	Output is correct
20	Correct	311 ms	227068 KB	Output is correct
21	Correct	5 ms	4300 KB	Output is correct
22	Correct	348 ms	209296 KB	Output is correct
23	Correct	379 ms	210700 KB	Output is correct
24	Correct	325 ms	213476 KB	Output is correct
25	Correct	331 ms	213484 KB	Output is correct
26	Correct	400 ms	210904 KB	Output is correct
27	Correct	347 ms	216072 KB	Output is correct
28	Correct	344 ms	215304 KB	Output is correct
29	Correct	327 ms	216176 KB	Output is correct
30	Correct	384 ms	225656 KB	Output is correct
31	Correct	400 ms	225512 KB	Output is correct
32	Correct	330 ms	209928 KB	Output is correct
33	Correct	394 ms	210816 KB	Output is correct
34	Correct	339 ms	208644 KB	Output is correct
35	Correct	340 ms	208664 KB	Output is correct
36	Correct	398 ms	210752 KB	Output is correct
37	Correct	333 ms	226952 KB	Output is correct
38	Correct	341 ms	226940 KB	Output is correct
39	Correct	400 ms	225528 KB	Output is correct
40	Correct	429 ms	227836 KB	Output is correct
41	Correct	711 ms	225316 KB	Output is correct
42	Correct	450 ms	223340 KB	Output is correct
43	Correct	0 ms	204 KB	Output is correct
44	Correct	5 ms	4428 KB	Output is correct
45	Correct	5601 ms	1689504 KB	Output is correct
46	Correct	4854 ms	1667644 KB	Output is correct
47	Correct	4858 ms	1668088 KB	Output is correct
48	Correct	4622 ms	1688892 KB	Output is correct
49	Correct	5629 ms	1689576 KB	Output is correct
50	Correct	2894 ms	1739000 KB	Output is correct
51	Correct	4645 ms	1680060 KB	Output is correct
52	Correct	2907 ms	1737216 KB	Output is correct
53	Correct	6217 ms	1804236 KB	Output is correct
54	Correct	3142 ms	1816024 KB	Output is correct
55	Correct	3470 ms	1803384 KB	Output is correct
56	Correct	6318 ms	1785856 KB	Output is correct
57	Correct	6332 ms	1788292 KB	Output is correct
58	Correct	6437 ms	1790692 KB	Output is correct
59	Correct	6664 ms	1793380 KB	Output is correct
60	Correct	6755 ms	1817312 KB	Output is correct
61	Correct	6833 ms	1829168 KB	Output is correct