Submission #438455

#	Time	Username	Problem	Language	Result	Execution time	Memory
438455		p_b_p_b	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3745 ms	342852 KiB

dungeons

#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 (stderr)

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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11