Submission #817463

#	Time	Username	Problem	Language	Result	Execution time	Memory
817463		I_Love_EliskaM_	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7021 ms	423860 KiB

dungeons

#include "dungeons.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second

const int N=4e5+55;
const int K=24;
struct up {
	ll v, x, mn;
};
up jump[N][K];
int d[N];

int to[N], x[N], s[N];

const int K2=19;
struct win {
	ll v, x, mx;
};
win go[N][K2];

int n;

void init(int _n, vector<int> _s, vector<int> p, vector<int> w, vector<int> l) {
	n=_n;

	for (int i=n-1; i>=0; --i) {
		d[i]=d[w[i]]+s[i];
	}
	forn(i,n) s[i]=_s[i]; s[n]=0;
	forn(i,n) to[i]=l[i]; to[n]=n;
	forn(i,n) x[i]=p[i]; x[n]=0;
	
	forn(i,n+1) jump[i][0]={to[i],x[i],min(s[i],s[to[i]]-x[i])};

	for (int j=1; j<K; ++j) {
		forn(i,n+1) {

			int u=i;
			auto a = jump[u][j-1];
			int v = a.v;
			auto b = jump[v][j-1];

			jump[i][j] = {b.v, a.x+b.x, min(a.mn, b.mn-a.x)};

		}
	}

	go[n][0] = { n, 0, 0 };
	forn(i,n) go[i][0] = { w[i], s[i], s[i] };

	for (int j=1; j<K2; ++j) {
		forn(i,n+1) {

			int u=i;
			auto a = go[u][j-1];
			int v = a.v;
			auto b = go[v][j-1];

			go[i][j] = { b.v, a.x+b.x, max(a.mx, b.mx-a.x) };

		}
	}

	//for (int j=0; j<3; ++j) {
	//	forn(i,n+1) cout<<i<<' '<<j<<": "<<jump[i][j].v<<' '<<jump[i][j].x<<' '<<jump[i][j].mn<<'\n';
	//}
	//for (int j=0; j<3; ++j) {
	//	forn(i,n+1) cout<<i<<' '<<j<<": "<<go[i][j].v<<' '<<go[i][j].x<<' '<<go[i][j].mx<<'\n';
	//}

}

long long simulate(int x, int z) {

	int u=x;
	ll ans=z;

	while (u<n) {

		for (int j=K-1; j>=0; --j) {
			if (ans >= jump[u][j].mn) continue;
			ans+=jump[u][j].x;
			u=jump[u][j].v;
		}
		if (ans<s[u]) {
			ans+=jump[u][0].x;
			u=jump[u][0].v;
			assert(ans>=s[u]);
		}
		
		for (int j=K2-1; j>=0; --j) {
			if (ans < go[u][j].mx) continue;
			ans += go[u][j].x;
			u = go[u][j].v;
		}

	}

	return ans;

}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:6:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define forn(i,n) for(int i=0; i<n; ++i)
      |                   ^~~
dungeons.cpp:39:2: note: in expansion of macro 'forn'
   39 |  forn(i,n) to[i]=l[i]; to[n]=n;
      |  ^~~~
dungeons.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  forn(i,n) to[i]=l[i]; to[n]=n;
      |                        ^~
dungeons.cpp:6:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define forn(i,n) for(int i=0; i<n; ++i)
      |                   ^~~
dungeons.cpp:40:2: note: in expansion of macro 'forn'
   40 |  forn(i,n) x[i]=p[i]; x[n]=0;
      |  ^~~~
dungeons.cpp:40:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  forn(i,n) x[i]=p[i]; x[n]=0;
      |                       ^

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