oj.uz

Submission #439672

# Submission time Handle Problem Language Result Execution time Memory
439672 2021-06-30T13:57:20 Z haojiandan Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4922 ms 971624 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=(4e5)+10;
int n,hd,tl,q[maxn],lg[maxn*2];
struct Tree {
	int a[maxn],in[maxn];
	ll w[maxn],dep[maxn],p[maxn]; bool cyc[maxn],vis[maxn];
	vector<int> son[maxn];
	int fa[maxn][20]; ll mn[maxn][20];
	void dfs(int u) {
		for (int v : son[u]) if (!cyc[v]) {
			dep[v]=dep[u]+p[v]; dfs(v);
		}
	}
	int cnt,L[maxn],R[maxn],tot,bel[maxn];
	ll all[maxn],pre[maxn*2],st[maxn*2][21];
	int rem[maxn*2],pos[maxn];
	ll query(int l,int r) {
		int j=lg[r-l+1];
		return min(st[l][j],st[r-(1<<j)+1][j]);
	}
	void build() {
		for (int i=1;i<=n;i++) in[a[i]]++,son[a[i]].push_back(i),fa[i][0]=a[i];
		//for (int i=1;i<=n;i++) printf("a[%d]=%d,w[%d]=%lld,p[%d]=%lld\n",i,a[i],i,w[i],i,p[i]);
		hd=1,tl=0;
		for (int i=1;i<=n;i++) if (!in[i]) q[++tl]=i;
		while (hd<=tl) {
			int x=q[hd]; hd++;
			int y=a[x];
			in[y]--; if (!in[y]) q[++tl]=y;
		}
		for (int i=1;i<=n;i++) if (in[i]) cyc[i]=1;//,printf("cyc=%d\n",i);
		for (int i=1;i<=n;i++) if (cyc[i]) {
			dfs(i); fa[i][0]=0;
			if (!vis[i]) {
				int x=i;
				cnt++; L[cnt]=tot+1;
				while (1) {
					bel[x]=cnt; all[cnt]+=p[x]; vis[x]=1;
					tot++; pos[x]=tot; rem[tot]=x;
					x=a[x]; if (x==i) break;
				}
				R[cnt]=tot;
				for (int j=L[cnt];j<=R[cnt];j++) rem[++tot]=rem[j];
				R[cnt]=tot;
				ll now=0;
				for (int j=L[cnt];j<=R[cnt];j++) {
					st[j][0]=w[rem[j]]-now;
					pre[j]=now;
					now+=p[rem[j]];
				}
			}
		}
		for (int i=1;i<=n;i++) mn[i][0]=dep[a[i]]+w[a[i]];
		for (int i=1;i<=20;i++) for (int j=1;j+(1<<i)-1<=tot;j++)
			st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		for (int i=1;i<=19;i++) for (int j=1;j<=n;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1],mn[j][i]=min(mn[fa[j][i-1]][i-1],mn[j][i-1]);
	}
	void solve(int &x,ll &now) {
	//	printf("x=%d,now=%lld\n",x,now);
		if (now>=w[x]) return;
		if (!cyc[x]) {
			int y=x;
			for (int i=19;i>=0;i--) if (fa[y][i]) {
				if (now+dep[x]<mn[y][i]) y=fa[y][i];
			}
			if (!cyc[y]) y=fa[y][0];
			now+=dep[x]-dep[y]; x=y;
			//printf("y=%d\n",y);
			if (now>=w[x]) return;
		}
		if (x==n) return;
	//	printf("%d\n",x);
		ll mn=query(pos[x],R[bel[x]]);
		ll bd=mn+pre[pos[x]]-now;
		int rd; if (bd<=0) rd=0; else if (bd%all[bel[x]]==0) rd=bd/all[bel[x]]; else rd=bd/all[bel[x]]+1;
		int y=pos[x]+1;
		for (int i=19;i>=0;i--) if (y+(1<<i)-1<=R[bel[x]]) {
			if (now-pre[pos[x]]+all[bel[x]]*rd<st[y][i]) y+=(1<<i);
		}
		now+=pre[y]-pre[pos[x]]+all[bel[x]]*rd;
		x=rem[y];
	}
} tr[4];
int s[maxn],w[maxn],p[maxn],nxt[maxn];
void init(int _n,vector<int> _s,vector<int> _p,vector<int> _w,vector<int> _l) {
	n=_n;
	for (int i=1;i<=n;i++) s[i]=_s[i-1],w[i]=_w[i-1]+1,p[i]=_p[i-1],nxt[i]=_l[i-1]+1;
	w[n+1]=nxt[n+1]=n+1; n++;
//	printf("MLE %d\n",sizeof(tr)/1024/1024);
	for (int i=2;i<=n*2;i++) lg[i]=lg[i>>1]+1;
//	puts("OK");
	for (int i=0;i<4;i++) {
		for (int j=1;j<=n;j++) {
			if (j==n||(s[j]>>(i*10))) tr[i].a[j]=nxt[j],tr[i].w[j]=s[j],tr[i].p[j]=p[j];
			else tr[i].a[j]=w[j],tr[i].w[j]=INF/10,tr[i].p[j]=s[j];
			
		}
		tr[i].build();
	}
//	puts("OK");
}
 
ll simulate(int x, int z) {
	x++; ll now=z;
	for (int i=0;i<4;i++) {
		while (now<(1LL<<(i*10+10))) {
			tr[i].solve(x,now);
		//	printf("%d %d %lld\n",i,x,now);
			assert(x);
			if (x==n) break;
			now+=s[x]; x=w[x]; if (x==n) break;
		}
	}
	return now;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38340 KB Output is correct
2 Correct 24 ms 38348 KB Output is correct
3 Correct 29 ms 40828 KB Output is correct
4 Correct 181 ms 99092 KB Output is correct
5 Correct 30 ms 40780 KB Output is correct
6 Correct 166 ms 98992 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39624 KB Output is correct
2 Correct 1707 ms 661900 KB Output is correct
3 Correct 1559 ms 664828 KB Output is correct
4 Correct 1524 ms 679900 KB Output is correct
5 Correct 1750 ms 514312 KB Output is correct
6 Correct 1614 ms 546504 KB Output is correct
7 Correct 1847 ms 821736 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39628 KB Output is correct
2 Correct 238 ms 100868 KB Output is correct
3 Correct 309 ms 100184 KB Output is correct
4 Correct 192 ms 103472 KB Output is correct
5 Correct 232 ms 101600 KB Output is correct
6 Correct 245 ms 101572 KB Output is correct
7 Correct 244 ms 101672 KB Output is correct
8 Correct 219 ms 103236 KB Output is correct
9 Correct 208 ms 100144 KB Output is correct
10 Correct 261 ms 103120 KB Output is correct
11 Correct 247 ms 103632 KB Output is correct
12 Correct 375 ms 155580 KB Output is correct
13 Correct 313 ms 154452 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39628 KB Output is correct
2 Correct 238 ms 100868 KB Output is correct
3 Correct 309 ms 100184 KB Output is correct
4 Correct 192 ms 103472 KB Output is correct
5 Correct 232 ms 101600 KB Output is correct
6 Correct 245 ms 101572 KB Output is correct
7 Correct 244 ms 101672 KB Output is correct
8 Correct 219 ms 103236 KB Output is correct
9 Correct 208 ms 100144 KB Output is correct
10 Correct 261 ms 103120 KB Output is correct
11 Correct 247 ms 103632 KB Output is correct
12 Correct 375 ms 155580 KB Output is correct
13 Correct 313 ms 154452 KB Output is correct
14 Correct 27 ms 39628 KB Output is correct
15 Correct 236 ms 100944 KB Output is correct
16 Correct 258 ms 102292 KB Output is correct
17 Correct 202 ms 104424 KB Output is correct
18 Correct 210 ms 104848 KB Output is correct
19 Correct 249 ms 101704 KB Output is correct
20 Correct 253 ms 114980 KB Output is correct
21 Correct 222 ms 103628 KB Output is correct
22 Correct 1336 ms 101804 KB Output is correct
23 Correct 303 ms 110248 KB Output is correct
24 Correct 382 ms 136960 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39628 KB Output is correct
2 Correct 238 ms 100868 KB Output is correct
3 Correct 309 ms 100184 KB Output is correct
4 Correct 192 ms 103472 KB Output is correct
5 Correct 232 ms 101600 KB Output is correct
6 Correct 245 ms 101572 KB Output is correct
7 Correct 244 ms 101672 KB Output is correct
8 Correct 219 ms 103236 KB Output is correct
9 Correct 208 ms 100144 KB Output is correct
10 Correct 261 ms 103120 KB Output is correct
11 Correct 247 ms 103632 KB Output is correct
12 Correct 375 ms 155580 KB Output is correct
13 Correct 313 ms 154452 KB Output is correct
14 Correct 27 ms 39628 KB Output is correct
15 Correct 236 ms 100944 KB Output is correct
16 Correct 258 ms 102292 KB Output is correct
17 Correct 202 ms 104424 KB Output is correct
18 Correct 210 ms 104848 KB Output is correct
19 Correct 249 ms 101704 KB Output is correct
20 Correct 253 ms 114980 KB Output is correct
21 Correct 222 ms 103628 KB Output is correct
22 Correct 1336 ms 101804 KB Output is correct
23 Correct 303 ms 110248 KB Output is correct
24 Correct 382 ms 136960 KB Output is correct
25 Correct 224 ms 100936 KB Output is correct
26 Correct 220 ms 102288 KB Output is correct
27 Correct 234 ms 100700 KB Output is correct
28 Correct 204 ms 100656 KB Output is correct
29 Correct 269 ms 101836 KB Output is correct
30 Correct 252 ms 112168 KB Output is correct
31 Correct 276 ms 115524 KB Output is correct
32 Correct 352 ms 127680 KB Output is correct
33 Correct 1136 ms 135188 KB Output is correct
34 Correct 1248 ms 133444 KB Output is correct
35 Correct 1189 ms 104340 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39624 KB Output is correct
2 Correct 1707 ms 661900 KB Output is correct
3 Correct 1559 ms 664828 KB Output is correct
4 Correct 1524 ms 679900 KB Output is correct
5 Correct 1750 ms 514312 KB Output is correct
6 Correct 1614 ms 546504 KB Output is correct
7 Correct 1847 ms 821736 KB Output is correct
8 Correct 29 ms 39628 KB Output is correct
9 Correct 238 ms 100868 KB Output is correct
10 Correct 309 ms 100184 KB Output is correct
11 Correct 192 ms 103472 KB Output is correct
12 Correct 232 ms 101600 KB Output is correct
13 Correct 245 ms 101572 KB Output is correct
14 Correct 244 ms 101672 KB Output is correct
15 Correct 219 ms 103236 KB Output is correct
16 Correct 208 ms 100144 KB Output is correct
17 Correct 261 ms 103120 KB Output is correct
18 Correct 247 ms 103632 KB Output is correct
19 Correct 375 ms 155580 KB Output is correct
20 Correct 313 ms 154452 KB Output is correct
21 Correct 27 ms 39628 KB Output is correct
22 Correct 236 ms 100944 KB Output is correct
23 Correct 258 ms 102292 KB Output is correct
24 Correct 202 ms 104424 KB Output is correct
25 Correct 210 ms 104848 KB Output is correct
26 Correct 249 ms 101704 KB Output is correct
27 Correct 253 ms 114980 KB Output is correct
28 Correct 222 ms 103628 KB Output is correct
29 Correct 1336 ms 101804 KB Output is correct
30 Correct 303 ms 110248 KB Output is correct
31 Correct 382 ms 136960 KB Output is correct
32 Correct 224 ms 100936 KB Output is correct
33 Correct 220 ms 102288 KB Output is correct
34 Correct 234 ms 100700 KB Output is correct
35 Correct 204 ms 100656 KB Output is correct
36 Correct 269 ms 101836 KB Output is correct
37 Correct 252 ms 112168 KB Output is correct
38 Correct 276 ms 115524 KB Output is correct
39 Correct 352 ms 127680 KB Output is correct
40 Correct 1136 ms 135188 KB Output is correct
41 Correct 1248 ms 133444 KB Output is correct
42 Correct 1189 ms 104340 KB Output is correct
43 Correct 26 ms 38416 KB Output is correct
44 Correct 29 ms 39716 KB Output is correct
45 Correct 2017 ms 535108 KB Output is correct
46 Correct 1717 ms 524744 KB Output is correct
47 Correct 1818 ms 523580 KB Output is correct
48 Correct 1843 ms 532984 KB Output is correct
49 Correct 2085 ms 537640 KB Output is correct
50 Correct 1591 ms 641056 KB Output is correct
51 Correct 1692 ms 530836 KB Output is correct
52 Correct 1535 ms 558520 KB Output is correct
53 Correct 2487 ms 706600 KB Output is correct
54 Correct 3237 ms 807808 KB Output is correct
55 Correct 4301 ms 793140 KB Output is correct
56 Correct 4602 ms 556664 KB Output is correct
57 Correct 4512 ms 557628 KB Output is correct
58 Correct 4922 ms 555936 KB Output is correct
59 Correct 4858 ms 558624 KB Output is correct
60 Correct 4170 ms 971084 KB Output is correct
61 Correct 4161 ms 971624 KB Output is correct