Maalarit

input/code.cpp: In function 'int main()':
input/code.cpp:110:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < tree[cur.first].size(); i++) {
                                        ^

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;

// If a is smaller, add zero
#ifndef max_zero
#define max_zero(a,b)            (((a) > (b)) ? (a) : (0))
#endif

#ifndef max
#define max(a,b)            (((a) > (b)) ? (a) : (b))
#endif


int
atoi (string c)
{
	stringstream s;
	int i;
	s << c;
	s >> i;
	return i;
}

/* goal is n+1, start 0 */

vector<int>
into_vec (string str, int size)
{

	vector<int> vec(size);
	istringstream ssin(str);
         int j = 0;
         while(ssin >> vec[j]) {
	     j++;
         }
	return vec;
	vec.push_back(-1);
}

int
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	string buf;
	int n, i, j;

	getline (cin, buf);
	n = atoi (buf);
	vector<pair<int, int>> tree[n*3];
	vector<int> vec;
	getline (cin, buf);
	vec = into_vec (buf, n);

	int c1, c2, c3;

	c1 = vec[0];
	c2 = 0;
	c3 = 0;

	tree[0].push_back({n+1, vec[1]});
	tree[0].push_back({1+(n*2), vec[1]});
	tree[n+1].push_back({2, vec[2]});
	tree[n+1].push_back({2+(n*2), vec[2]});
	tree[(2*n)+1].push_back({2, vec[2]});
	tree[(2*n)+1].push_back({2+n, vec[2]});
	for (i = 2; i < n-1; i++) {
		tree[i].push_back({n+i+1, vec[i+1]});
		tree[i].push_back({(2*n)+i+1, vec[i+1]});

		tree[n+i].push_back({i+1, vec[i+1]});
		tree[n+i].push_back({(2*n)+i+1, vec[i+1]});

		tree[(2*n)+i].push_back({n+i+1, vec[i+1]});
		tree[(2*n)+i].push_back({i+1, vec[i+1]});
	}

	tree[n-1].push_back({3*n, 0});

	tree[(2*n)-1].push_back({3*n, 0});

	tree[(3*n)-1].push_back({3*n, 0});

	/* Djikstra */
	priority_queue<pair<int, int> > frontier;
	frontier.push({0, c1});
	map<int, int> came_from;
	map<int, int> cost_so_far;
	came_from.insert(pair<int, int>(0, NULL));
	cost_so_far.insert(pair<int, int>(0, vec[0]));
	
	/* loop */
	while (!frontier.empty()) {
		auto cur = frontier.top();
		frontier.pop();
		if (cur.first == n*3) {
			break;
		}

		for (i = 0; i < tree[cur.first].size(); i++) {
			int tmp, next, cost;
			next = tree[cur.first][i].first;
			if (next < n) {
				j = 0;
				tmp = next;
			} else if (next < 2*n) {
				j = 1;
				tmp = next-n-1;
			} else {
				j = 2;
				tmp = next-(2*n)-1;
			}

			if (j == 0) {
				cost = c1;
			} else if (j == 1) {
				cost = c2;
			} else {
				 cost = c3;
			}

			int new_cost = cost_so_far[cur.first] + max_zero(vec[tmp], cost);
			if (cost_so_far.find(next) == cost_so_far.end() || new_cost < cost_so_far[next]) {
				if (cost < vec[tmp]) {
					if (j == 0) {
						c1 = vec[tmp];
						priority_queue <pair<int, int> > f1;
						f1.push({0, 0});
						swap (f1, frontier);
						while (!f1.empty()) {
							auto nn = f1.top();
							f1.pop();
							if (nn.first < n) {
								frontier.push({nn.first, 0});
							} else {
								frontier.push(nn);
							}
						}
					} else if (j == 1) {
						c2 = vec[tmp];
						priority_queue <pair<int, int> > f1;
						f1.push({0, 0});
						swap (f1, frontier);
						while (!f1.empty()) {
							auto nn = f1.top();
							f1.pop();
							if (nn.first < 2*n && nn.first >= n) {
								frontier.push({nn.first, 0});
							} else {
								frontier.push(nn);
							}
						}
					} else {
						 c3 = vec[tmp];
						priority_queue <pair<int, int> > f1;
						f1.push({0, 0});
						swap (f1, frontier);
						while (!f1.empty()) {
							auto nn = f1.top();
							f1.pop();
							if (nn.first < 3*n && nn.first >= 2*n) {
								frontier.push({nn.first, 0});
							} else {
								frontier.push(nn);
							}
						}
					}
				}

				int priority;
				cost_so_far.insert(pair<int, int>(next, new_cost));
				priority = new_cost;
				frontier.push({next, priority});
				came_from.insert(pair<int, int>(next, cur.first));
			}
		}
	}
	int cur = 3*n;
	vector<int> path = {cur};
	while (cur != 0) {
		cur = came_from[cur];
		path.push_back(cur);
	}
	cout << c1+c2+c3 << endl;
	for (i = path.size()-1; i > 0; i--) {
		int nx = path[i];
		if (nx < n) {
			cout << "1 ";
		} else if (nx < 2*n) {
			cout << "2 ";
		} else {
			cout << "3 ";
		}
	}

	return 0;
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 2

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER

Test 16

Group: 3

Verdict: WRONG ANSWER

Test 17

Group: 3

Verdict: WRONG ANSWER

Test 18

Group: 3

Verdict: WRONG ANSWER

Test 19

Group: 4

Verdict: WRONG ANSWER

Test 20

Group: 4

Verdict: WRONG ANSWER

Test 21

Group: 4

Verdict: WRONG ANSWER

Test 22

Group: 4

Verdict: WRONG ANSWER

Test 23

Group: 4

Verdict: WRONG ANSWER

Test 24

Group: 4

Verdict: WRONG ANSWER