Submission #1216427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216427		thelegendary08	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	618 ms	326856 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
using namespace std;
const int lg = 30;
struct Node{
	int nxt, sum, req;
};
vector<signed> s,p,w,l; int n; vi type;
vector<vector<Node>> jmp; vi rngs;
vi pv;
void init(signed n, std::vector<signed> s, std::vector<signed> p, std::vector<signed> w, std::vector<signed> l) {
	::s=s; ::p=p; ::w=w; ::l=l; ::n=n;
	set<int>si;
	f0r(i,n){
		si.insert(s[i]);
	}
	for(auto u : si){
		rngs.pb(u);
	}
	type.resize(n); pv.resize(n); f0r(i,n)pv[i] = -1;
	f0r(i,n){
		f0r(j, rngs.size()){
			if(rngs[j] == s[i]){
				type[i] = j;
			}
		}
	}
	
	vi tmp(n);
	jmp.resize(n);
	f0r(i,n){
		jmp[i].resize(lg);
	}
	
	f0r(i,n){
		jmp[i][0] = {w[i], s[i], s[i]};
	}
	
	FOR(j, 1, lg){
		f0r(i,n){
			if(jmp[i][j-1].nxt == n)jmp[i][j] = jmp[i][j-1];
			else{
				int nx = jmp[jmp[i][j-1].nxt][j-1].nxt;
				int su = jmp[jmp[i][j-1].nxt][j-1].sum + jmp[i][j-1].sum;
				int rq;
				if(jmp[jmp[i][j-1].nxt][j-1].req <= jmp[i][j-1].sum + jmp[i][j-1].req){
					rq = jmp[i][j-1].req;
				}
				else{
					rq = jmp[jmp[i][j-1].nxt][j-1].req - jmp[i][j-1].sum;
				}
				jmp[i][j] = {nx, su, rq};
			}
		}
	}
	// cout<<jmp[1][1].req<<' '<<jmp[1][1].sum<<'\n';
	// dout2(jmp[0][0][0].first, jmp[0][0][0].second);
	
	return;
}

long long simulate(signed x, signed z) {
	int cur = x;
	int a = z;
	vi mod;
	int pre = -1;
	set<pii>thing;
	while(cur != n){
		// dout(curtype);
		// dout2(cur,a);
		for(int i = lg - 1; i>=0; i--){
			if(a >= jmp[cur][i].req){
				a += jmp[cur][i].sum;
				cur = jmp[cur][i].nxt;
				// cout<<a<<' '<<cur<<"SEDF"<<endl;
			}
			if(cur == n)break;
		}
		// dout2(cur,a);
		if(cur == n)break;
		if(pre == cur || (!thing.empty() && (*thing.begin()).first == s[cur])){
			thing.erase(mp(s[cur], cur));
			int dif = a - pv[cur];
			a += (s[cur] - a + dif - 1)/ dif * dif;
			a += s[cur];
			cur = w[cur];
			while(!thing.empty()){
				if((*thing.begin()).first > a)break;
				thing.erase(thing.begin());
			}
		}
		else{
			mod.pb(cur);
			thing.insert(mp(s[cur], cur));
			pre = cur;
			pv[cur] = a;
			a += p[cur];
			cur = l[cur];
		}
		
	}
	// vout(mod);
	for(auto u : mod)pv[u] = -1;
	// dout(a);
	return a;
}

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