제출 #829388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
829388		fatemetmhr	던전 (IOI21_dungeons)	C++17	37 / 100	7046 ms	73688 KiB

dungeons

// Be Name Khoda //


#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define MAX(x, y)  ((x) > (y) ? (x) : (y))
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
#define debug(x)   cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)     (x).begin(), (x).end()
#define fi         first
#define se         second
#define pb         push_back
#define mp         make_pair

typedef long long ll;

const int maxn5 = 4e5 + 10;
const int ssq   = 3200;

int n, rt, cmp[maxn5];
ll h[maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
vector <int> adj[maxn5];

void dfs(int v){
	cmp[v] = rt;
	for(auto u : adj[v]){
		h[u] = h[v] + s[u];
		dfs(u);
	}
}

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
	n = nn;
	for(int i = 0; i < n; i++){
		s[i] = ss[i];
		p[i] = pp[i];
		w[i] = ww[i];
		l[i] = ll[i];
		if(s[i] < ssq)
			adj[w[i]].pb(i);
	}
	for(int i = 0; i < n; i++) if(s[i] >= ssq){
		rt = i;
		dfs(i);
	}
	rt = n;
	dfs(n);
	return;
}

long long simulate(int x, int zz) {
	ll ret = zz;
	while(x < n && ret < ssq){
		if(ret < s[x]){
			ret += p[x];
			x = l[x];
		}
		else{
			ret += s[x];
			x = w[x];
		}
	}
	while(x < n){
		ret += h[x];
		x = cmp[x];
		if(x < n){
			if(ret < s[x]){
				ret += p[x];
				x = l[x];
			}
			else{
				ret += s[x];
				x = w[x];
			}
		}
	}
	return ret;
}

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