Submission #60468

#	Time	Username	Problem	Language	Result	Execution time	Memory
60468		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1064 ms	263168 KiB

skyscraper

#include <bits/stdc++.h>

struct QEntry
{
	int building;
	int doge;
	int cost;
};

bool visited[30000][30000];

int main()
{
	int numBuildings, numDoges;
	std::cin >> numBuildings;
	std::cin >> numDoges;
	
	std::vector<std::vector<int>> dogesInBuildings(numBuildings);
	
	std::vector<int> dogePositions(numDoges);
	std::vector<int> dogePowers(numDoges);
	for (int i = 0; i < numDoges; i++)
	{
		std::cin >> dogePositions[i];
		std::cin >> dogePowers[i];
		
		dogesInBuildings[dogePositions[i]].push_back(i);
	}
	
	std::deque<QEntry> q;
	
	q.push_back(QEntry { dogePositions[0], 0, 0 });
	while (!q.empty())
	{
		QEntry entry = q.front();
		q.pop_front();
		
		if (visited[entry.building][entry.doge])
			continue;
		if (entry.doge == 1)
		{
			std::cout << entry.cost << std::endl;
			return 0;
		}
		
		visited[entry.building][entry.doge] = true;
		
		for (int d : dogesInBuildings[entry.building])
		{
			if (visited[entry.building][d])
				continue;
			q.push_front(QEntry { entry.building, d, entry.cost });
		}
		
		int pBuilding = entry.building - dogePowers[entry.doge];
		if (pBuilding >= 0 && !visited[pBuilding][entry.doge])
		{
			q.push_back(QEntry { pBuilding, entry.doge, entry.cost + 1 });
		}
		
		int nBuilding = entry.building + dogePowers[entry.doge];
		if (nBuilding < numBuildings && !visited[nBuilding][entry.doge])
		{
			q.push_back(QEntry { nBuilding, entry.doge, entry.cost + 1 });
		}
	}
	
	std::cout << "-1" << std::endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43