Submission #439278

#	Time	Username	Problem	Language	Result	Execution time	Memory
439278		haojiandan	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	7091 ms	271044 KiB

dungeons

#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,s[maxn],w[maxn],p[maxn],nxt[maxn];
int in[maxn],Q[maxn];
bool cyc[maxn];
vector<int> son[maxn],s2[maxn];
int fa[maxn][20],f2[maxn][20];
ll dep[maxn],mn[maxn][20],mx[maxn][20],sd[maxn];
bool vis[maxn];
void dfs2(int u) {
	for (int v : s2[u]) sd[v]=sd[u]+s[v],dfs2(v);
}
int lsh[maxn],N;
void dfs(int u) {
	for (int v : son[u]) if (!cyc[v]) {
		dep[v]=dep[u]+p[v];
		dfs(v);
	}
}
int bel[maxn],cnt,L[maxn],R[maxn],pos[maxn];
ll st[maxn*2][21],pre[maxn*2],all[maxn];
int rem[maxn*2],lg[maxn*2],tot;

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,lsh[++N]=s[i];
	sort(lsh+1,lsh+N+1);
	N=unique(lsh+1,lsh+N+1)-lsh-1;
	
	nxt[n+1]=n+1;
	for (int i=1;i<=n+1;i++) in[nxt[i]]++;
	int hd=1,tl=0;
	for (int i=1;i<=n+1;i++) if (!in[i]) Q[++tl]=i;
	while (hd<=tl) {
		int x=Q[hd]; hd++;
		int y=nxt[x]; in[y]--; if (!in[y]) Q[++tl]=y;
	}
	for (int i=1;i<=n+1;i++) cyc[i]=(in[i]>0);
	for (int i=1;i<=n;i++) son[nxt[i]].push_back(i),s2[w[i]].push_back(i);
	dfs2(n+1);
	for (int i=2;i<maxn*2;i++) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n+1;i++) if (cyc[i]) {
		dfs(i);
		if (i!=n+1&&!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=nxt[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]=s[rem[j]]-now;
				pre[j]=now;
				now+=p[rem[j]];
			}
		}
	}
	//puts("OK");
	//for (int i=1;i<=tot;i++) printf("%d ",rem[i]); puts("");
	//for (int i=1;i<=tot;i++) printf("%lld ",st[i][0]); puts("");
	//for (int i=1;i<=tot;i++) printf("%lld ",pre[i]); puts("");
	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<=n+1;i++) {
		if (cyc[i]) mn[i][0]=INF,fa[i][0]=0;
		else mn[i][0]=s[nxt[i]]+dep[nxt[i]],fa[i][0]=nxt[i];
		f2[i][0]=w[i]; mx[i][0]=sd[w[i]]+s[w[i]];
	}
	for (int i=1;i<=19;i++) for (int j=1;j<=n+1;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]);
		f2[j][i]=f2[f2[j][i-1]][i-1],mx[j][i]=max(mx[f2[j][i-1]][i-1],mx[j][i-1]);
	}
	//puts("OK");
	
}
ll query(int l,int r) {
	int j=lg[r-l+1];
	return min(st[l][j],st[r-(1<<j)+1][j]);
}
ll simulate(int x, int z) {
	ll now=z; x++;
	int sz=0;
	while (x!=n+1) {
		//printf("x=%d,now=%lld\n",x,now);
		//assert(x);
		sz++;
		if (now>=s[x]) {
			if (N<=5) { now+=s[x]; x=w[x]; continue; }
			int y=x;
			for (int i=19;i>=0;i--) if (f2[y][i]) {
				if (sd[x]+now>=mx[y][i]) y=f2[y][i];
			}
			if (y!=n+1) y=f2[y][0];
			now+=sd[x]-sd[y];
			x=y;
			continue;
		}
		if (cyc[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];
			
		} else {
			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("sz=%d\n",sz);
	return now;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11