CSES - Datatähti 2020 alku - Results
Submission details
Task:Ruudukko
Sender:ph
Submission time:2019-10-06 15:59:48 +0300
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1--details
#2--details
#3--details
#4--details
#5--details
#6--details

Code

#include<bits/stdc++.h>
using namespace std;

struct GNode {
	unsigned long long pos;
	vector<unsigned long long> childs;
};

struct Node {
	unsigned long long pos;
	vector<unsigned long long> childs;
	unsigned long long g;
	unsigned long long h;
	unsigned long long f;
	Node(unsigned long long _pos, vector<unsigned long long> _childs, unsigned long long _g, unsigned long long _h, unsigned long long _f) {
		pos = _pos;
		childs = _childs;
		g = _g;
		h = _h;
		f = _f;
	}
};

struct find_pos {
	unsigned long long pos;
	find_pos(unsigned long long pos) : pos(pos) {}
	bool operator () (const Node &n) const {
		return n.pos == pos;
	}
};

bool compareNodes(const Node &a, const Node &b) {
	return !(a.f < b.f);
}

int main() {
	unsigned long long n;
	cin >> n;
	vector<unsigned long long> d;
	vector<unsigned long long> c;
	for (unsigned long long i = 0; i < n; i++) {
		unsigned long long t;
		cin >> t;
		d.push_back(t);
	}
	for (unsigned long long i = 0; i < n-1; i++) {
		unsigned long long t;
		cin >> t;
		c.push_back(t);
	}
	d.push_back(0);
	c.push_back(0);
	vector<GNode> graph;
	for (unsigned long long i = 0; i < d.size(); i++) {
		GNode t;
		t.pos = i;
		for (unsigned long long j = 1; j < d[i] + 1; j++) {
			if (i + j <= n) {
				t.childs.push_back(i + j);
			}
		}
		graph.push_back(t);
	}
	
	
	vector<Node> oNodes;
	vector<Node> cNodes;
	Node t(0, graph[0].childs, 0, 0, 0);
	oNodes.push_back(t);

	bool done = false;
	
	while (oNodes.size() != 0 && !done) {
		sort(oNodes.begin(), oNodes.end(), compareNodes);
		Node current = oNodes.back();
		oNodes.pop_back();
		cNodes.push_back(current);
		if (current.pos == n) {
			cout << current.g;
			done = true;
			break;
		}
		
		vector<unsigned long long> childs = current.childs;
		for (auto child : childs) {
			Node newNode(child, graph[child].childs, current.g + c[child - 1], n - child, (current.g + c[child - 1]) + (n - child));
			auto it = find_if(oNodes.begin(), oNodes.end(), find_pos(child));
			if (it != oNodes.end()) {
				if (it->g < newNode.g) {
					continue;
				} 
			}
			oNodes.push_back(newNode);
		}
	}
}

Test details

Test 1

Verdict:

input
1

correct output

user output
(empty)

Test 2

Verdict:

input
2

correct output
1 2 
2 1 

user output
(empty)

Test 3

Verdict:

input
5

correct output
1 2 3 4 5 
2 1 4 3 6 
3 4 1 2 7 
4 3 2 1 8 
5 6 7 8 1 

user output
(empty)

Test 4

Verdict:

input
42

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)

Test 5

Verdict:

input
99

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)

Test 6

Verdict:

input
100

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)