oj.uz

Submission #438455

# Submission time Handle Problem Language Result Execution time Memory
438455 2021-06-28T03:30:23 Z p_b_p_b Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3745 ms 342852 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 404000
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cerr<<clock()/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n;

struct hh{int t,nxt;}edge[sz<<1];
int head[sz],ecnt;
void make_edge(int f,int t){edge[++ecnt]=(hh){t,head[f]};head[f]=ecnt;}
void CLR(){rep(i,1,n) head[i]=0;ecnt=0;}
#define v edge[i].t

int deg[sz];
pair<ll,int> st[sz]; int tp;
int son[sz],siz[sz];
struct TREE
{
	int a[sz]; ll dt[sz],W[sz]; // ×ßµ½ÄÄ¡¢¼Ó¶àÉÙ¡¢ÐèÒª¶àÉÙ 
	int rt[sz];
	
	void topo()
	{
		rep(i,1,n) deg[i]=0; rep(i,1,n) ++deg[a[i]];
		static int q[sz]; int l=1,r=0;
		rep(i,1,n) if (!deg[i]) q[++r]=i;
		while (l<=r)
		{
			int x=q[l++];
			if (!--deg[a[x]]) q[++r]=a[x];
		}
		static int vis[sz]; rep(i,1,n) vis[i]=0;
		rep(i,1,n) if (deg[i]&&!vis[i])
		{
			rt[i]=i;
			for (int x=i;!vis[x];x=a[x]) vis[x]=1;
		}
		rep(i,1,n) if (!rt[i]) make_edge(a[i],i);
	}
	
	ll D[sz],mn[sz]; int fa[sz]; // fa£ºÊ÷Éϵĸ¸Ç× 
	void dfs(int x)
	{
		W[x]+=D[x]; chkmin(mn[x],W[x]);
		int pos=-1,_tp=tp; auto tmp=st[0];
		pos=lower_bound(st+1,st+tp+1,MP(W[x],0))-st; tmp=st[pos]; st[pos]=MP(W[x],x);
		fa[x]=st[pos-1].sec; tp=pos;
		go(x) rt[v]=rt[x],D[v]=D[x]+dt[v],mn[v]=mn[x],dfs(v);
		tp=_tp; st[pos]=tmp;
	}
	
	int dfn[sz],pre[sz],top[sz],cc;  ll ww[sz];
	void dfs1(int x)
	{
		siz[x]=1,son[x]=0;
		go(x)
		{
			dfs1(v); siz[x]+=siz[v];
			if (siz[v]>siz[son[x]]) son[x]=v;
		}
	}
	void dfs2(int x,int tp)
	{
		top[x]=tp; pre[dfn[x]=++cc]=x; ww[cc]=W[x];
		if (son[x]) dfs2(son[x],tp);
		go(x) if (v!=son[x]) dfs2(v,v);
	}
	
	void init()
	{
		CLR();
		topo();
		rep(i,1,n) mn[i]=1e18;
		rep(i,1,n) if (rt[i]==i) dfs(i);
		CLR();
		rep(i,1,n) if (fa[i]) make_edge(fa[i],i);
		rep(i,1,n) if (!fa[i]) dfs1(i),dfs2(i,i);
	}
	
	int qq(int x,ll w)
	{
		while (x&&w<W[top[x]]) x=fa[top[x]];
		if (!x) return 0;
		int p=upper_bound(ww+dfn[top[x]],ww+dfn[x]+1,w)-ww-1;
		return pre[p];
	}
	int query(int x,ll &w)
	{
		w+=D[x];
		int t=qq(x,w);
		if (t) return w-=D[t],t;
		x=rt[x],w+=dt[x],x=a[x]; if (x==n) return x;
		if (w+D[x]>=mn[x]) return t=qq(x,w+D[x]),w+=D[x]-D[t],t;
		ll s=D[x]+dt[rt[x]];
		ll c=(mn[x]-(w+D[x])-1)/s+1; w+=c*s+D[x];
		t=qq(x,w); assert(t); return w-=D[t],t;
	}
}tr[9];


ll S[sz],P[sz]; int W[sz],L[sz];
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l)
{
	n=_n; chktime();
	rep(i,0,n-1) S[i+1]=_s[i],P[i+1]=_p[i],W[i+1]=_w[i]+1,L[i+1]=_l[i]+1;
	S[n+1]=0,W[n+1]=L[n+1]=n+1; ++n;
	rep(i,0,8)
	{
		rep(k,1,n)
			if ((S[k]>>(i*3))||k==n) tr[i].a[k]=L[k],tr[i].dt[k]=P[k],tr[i].W[k]=S[k];
			else tr[i].a[k]=W[k],tr[i].dt[k]=S[k],tr[i].W[k]=1e17;
		tr[i].init(); chktime();
	}
}

long long simulate(int x, int z)
{
	++x; ll w=z;
	rep(i,0,8) while (w<(1<<(i*3+3))&&x!=n) x=tr[i].query(x,w),assert(w>=S[x]),w+=S[x],x=W[x];
	assert(x==n);
	return w;
}

#ifdef NTFOrz

namespace ____
{
static int n, q;
static std::vector<int> s, p, z;
static std::vector<int> w, l, x;
static std::vector<long long> answer;

int main() {
	assert(scanf("%d %d", &n, &q) == 2);
	s.resize(n);
	p.resize(n);
	w.resize(n);
	l.resize(n);
    x.resize(q);
    z.resize(q);
    answer.resize(q);

	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &s[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &p[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &w[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &l[i]) == 1);
	}


    init(n, s, p, w, l);
    chktime();

    for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &z[i]) == 2);
		answer[i] = simulate(x[i], z[i]);
    }
    fclose(stdin);
chktime();
//	puts("ok");
    for (int i = 0; i < q; i++) {
//        printf("%lld\n", answer[i]);
    }
    fclose(stdout);
    return 0;
}
}

int main(){return file(),____::main();}

#endif

Compilation message

dungeons.cpp: In function 'void my_std::print(int)':
dungeons.cpp:33:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |   if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
      |   ^~
dungeons.cpp:33:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |   if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
      |                     ^~
dungeons.cpp:35:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   35 |   while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
      |   ^~~~~
dungeons.cpp:35:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   35 |   while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
      |                                       ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 5 ms 2380 KB Output is correct
4 Correct 136 ms 33608 KB Output is correct
5 Correct 5 ms 2380 KB Output is correct
6 Correct 120 ms 33524 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 1248 ms 315688 KB Output is correct
3 Correct 1326 ms 342776 KB Output is correct
4 Correct 1793 ms 342852 KB Output is correct
5 Correct 2737 ms 261488 KB Output is correct
6 Correct 1299 ms 315716 KB Output is correct
7 Correct 886 ms 342720 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 189 ms 34444 KB Output is correct
3 Correct 171 ms 41120 KB Output is correct
4 Correct 138 ms 44516 KB Output is correct
5 Correct 129 ms 41060 KB Output is correct
6 Correct 204 ms 34376 KB Output is correct
7 Correct 193 ms 34404 KB Output is correct
8 Correct 150 ms 44448 KB Output is correct
9 Correct 157 ms 34400 KB Output is correct
10 Correct 159 ms 44484 KB Output is correct
11 Correct 173 ms 44264 KB Output is correct
12 Correct 210 ms 44484 KB Output is correct
13 Correct 139 ms 44512 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 189 ms 34444 KB Output is correct
3 Correct 171 ms 41120 KB Output is correct
4 Correct 138 ms 44516 KB Output is correct
5 Correct 129 ms 41060 KB Output is correct
6 Correct 204 ms 34376 KB Output is correct
7 Correct 193 ms 34404 KB Output is correct
8 Correct 150 ms 44448 KB Output is correct
9 Correct 157 ms 34400 KB Output is correct
10 Correct 159 ms 44484 KB Output is correct
11 Correct 173 ms 44264 KB Output is correct
12 Correct 210 ms 44484 KB Output is correct
13 Correct 139 ms 44512 KB Output is correct
14 Correct 3 ms 1740 KB Output is correct
15 Correct 164 ms 34396 KB Output is correct
16 Correct 185 ms 34328 KB Output is correct
17 Correct 155 ms 39440 KB Output is correct
18 Correct 137 ms 39388 KB Output is correct
19 Correct 191 ms 34448 KB Output is correct
20 Correct 163 ms 41060 KB Output is correct
21 Correct 185 ms 41156 KB Output is correct
22 Correct 139 ms 37700 KB Output is correct
23 Correct 172 ms 42720 KB Output is correct
24 Correct 262 ms 44312 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 189 ms 34444 KB Output is correct
3 Correct 171 ms 41120 KB Output is correct
4 Correct 138 ms 44516 KB Output is correct
5 Correct 129 ms 41060 KB Output is correct
6 Correct 204 ms 34376 KB Output is correct
7 Correct 193 ms 34404 KB Output is correct
8 Correct 150 ms 44448 KB Output is correct
9 Correct 157 ms 34400 KB Output is correct
10 Correct 159 ms 44484 KB Output is correct
11 Correct 173 ms 44264 KB Output is correct
12 Correct 210 ms 44484 KB Output is correct
13 Correct 139 ms 44512 KB Output is correct
14 Correct 3 ms 1740 KB Output is correct
15 Correct 164 ms 34396 KB Output is correct
16 Correct 185 ms 34328 KB Output is correct
17 Correct 155 ms 39440 KB Output is correct
18 Correct 137 ms 39388 KB Output is correct
19 Correct 191 ms 34448 KB Output is correct
20 Correct 163 ms 41060 KB Output is correct
21 Correct 185 ms 41156 KB Output is correct
22 Correct 139 ms 37700 KB Output is correct
23 Correct 172 ms 42720 KB Output is correct
24 Correct 262 ms 44312 KB Output is correct
25 Correct 148 ms 33584 KB Output is correct
26 Correct 186 ms 34320 KB Output is correct
27 Correct 161 ms 34372 KB Output is correct
28 Correct 152 ms 34428 KB Output is correct
29 Correct 202 ms 34372 KB Output is correct
30 Correct 173 ms 44496 KB Output is correct
31 Correct 179 ms 44484 KB Output is correct
32 Correct 213 ms 39280 KB Output is correct
33 Correct 350 ms 34756 KB Output is correct
34 Correct 395 ms 34724 KB Output is correct
35 Correct 317 ms 39136 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 1248 ms 315688 KB Output is correct
3 Correct 1326 ms 342776 KB Output is correct
4 Correct 1793 ms 342852 KB Output is correct
5 Correct 2737 ms 261488 KB Output is correct
6 Correct 1299 ms 315716 KB Output is correct
7 Correct 886 ms 342720 KB Output is correct
8 Correct 3 ms 1740 KB Output is correct
9 Correct 189 ms 34444 KB Output is correct
10 Correct 171 ms 41120 KB Output is correct
11 Correct 138 ms 44516 KB Output is correct
12 Correct 129 ms 41060 KB Output is correct
13 Correct 204 ms 34376 KB Output is correct
14 Correct 193 ms 34404 KB Output is correct
15 Correct 150 ms 44448 KB Output is correct
16 Correct 157 ms 34400 KB Output is correct
17 Correct 159 ms 44484 KB Output is correct
18 Correct 173 ms 44264 KB Output is correct
19 Correct 210 ms 44484 KB Output is correct
20 Correct 139 ms 44512 KB Output is correct
21 Correct 3 ms 1740 KB Output is correct
22 Correct 164 ms 34396 KB Output is correct
23 Correct 185 ms 34328 KB Output is correct
24 Correct 155 ms 39440 KB Output is correct
25 Correct 137 ms 39388 KB Output is correct
26 Correct 191 ms 34448 KB Output is correct
27 Correct 163 ms 41060 KB Output is correct
28 Correct 185 ms 41156 KB Output is correct
29 Correct 139 ms 37700 KB Output is correct
30 Correct 172 ms 42720 KB Output is correct
31 Correct 262 ms 44312 KB Output is correct
32 Correct 148 ms 33584 KB Output is correct
33 Correct 186 ms 34320 KB Output is correct
34 Correct 161 ms 34372 KB Output is correct
35 Correct 152 ms 34428 KB Output is correct
36 Correct 202 ms 34372 KB Output is correct
37 Correct 173 ms 44496 KB Output is correct
38 Correct 179 ms 44484 KB Output is correct
39 Correct 213 ms 39280 KB Output is correct
40 Correct 350 ms 34756 KB Output is correct
41 Correct 395 ms 34724 KB Output is correct
42 Correct 317 ms 39136 KB Output is correct
43 Correct 1 ms 1100 KB Output is correct
44 Correct 4 ms 1740 KB Output is correct
45 Correct 3245 ms 263096 KB Output is correct
46 Correct 2860 ms 262892 KB Output is correct
47 Correct 2962 ms 263172 KB Output is correct
48 Correct 2553 ms 317020 KB Output is correct
49 Correct 3404 ms 262964 KB Output is correct
50 Correct 1220 ms 315636 KB Output is correct
51 Correct 2546 ms 302184 KB Output is correct
52 Correct 1246 ms 315860 KB Output is correct
53 Correct 3071 ms 300616 KB Output is correct
54 Correct 1552 ms 263776 KB Output is correct
55 Correct 1712 ms 265016 KB Output is correct
56 Correct 3238 ms 299680 KB Output is correct
57 Correct 3745 ms 299688 KB Output is correct
58 Correct 3260 ms 299628 KB Output is correct
59 Correct 3381 ms 299476 KB Output is correct
60 Correct 3738 ms 275188 KB Output is correct
61 Correct 3641 ms 291440 KB Output is correct