oj.uz

Submission #834260

# Submission time Handle Problem Language Result Execution time Memory
834260 2023-08-22T12:24:25 Z Abrar_Al_Samit Dungeons Game (IOI21_dungeons) C++17
26 / 100
 477 ms 145628 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int nax = 4e5 + 3;
int n;
vector<int>s, p, w, l;
int nxtBig[nax];
long long sum_toNext[nax], sum_toN[nax];

vector<int>g[nax];

set<pair<int,int>> dfs(int v, long long sum = 0) {
	if(v < n) sum += s[v];
	sum_toN[v] = sum;

	set<pair<int,int>>me;
	for(int u : g[v]) {
		auto he = dfs(u, sum);
		if(me.size()<he.size()) me.swap(he);
		for(auto e : he) me.insert(e);
	}
	
	while(!me.empty()) {
		auto [val, he] = *me.begin();
		if(v < n && val >= s[v]) break;

		nxtBig[he] = v;
		sum_toNext[he] = sum_toN[he] - sum_toN[v];

		me.erase(me.begin());
	}
	if(v < n) me.insert({s[v], v});
	return me;
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N, s = S, p = P, w = W, l = L;

	for(int i=0; i<n; ++i) {
		nxtBig[i] = -1;
	}
	for(int i=0; i<n; ++i) {
		g[w[i]].push_back(i);
	}
	dfs(n);
}

const int anax = 1e7;
long long simulate(int x, int z) {

	long long cz = z;
	while(x < n && cz < anax) {
		if(cz >= s[x]) {
			cz += sum_toNext[x];
			x = nxtBig[x];
		} else {
			cz += s[x];
			x = l[x];			
		}
	}
	cz += sum_toN[x];
	return cz;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 275 ms 103272 KB Output is correct
3 Correct 242 ms 139692 KB Output is correct
4 Correct 260 ms 145628 KB Output is correct
5 Correct 477 ms 59308 KB Output is correct
6 Correct 251 ms 109528 KB Output is correct
7 Correct 274 ms 136028 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 275 ms 103272 KB Output is correct
3 Correct 242 ms 139692 KB Output is correct
4 Correct 260 ms 145628 KB Output is correct
5 Correct 477 ms 59308 KB Output is correct
6 Correct 251 ms 109528 KB Output is correct
7 Correct 274 ms 136028 KB Output is correct
8 Incorrect 6 ms 9840 KB Output isn't correct
9 Halted 0 ms 0 KB -