Submission #317499

#	Time	Username	Problem	Language	Result	Execution time	Memory
317499		MahdiBahramian	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	0 / 100	99 ms	149240 KiB

skyscraper

#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define F first
#define S second
#define var auto
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Max = 30010;
const int Sq = 200;
const int INF = 1000000010;

vector<int> pws[Max];
ll dist[Max][Sq + 10];
vector<pair<pii, int> > N[Max][Sq + 10];

void DFS(pii v)
{
	//cout << "(" << v.F << "," << v.S << ") = " << dist[v.F][v.S] << "\n";
	for(var u : N[v.F][v.S])
		if(dist[u.F.F][u.F.S] > dist[v.F][v.S] + u.S)
		{
			dist[u.F.F][u.F.S] = dist[v.F][v.S] + u.S;
			DFS(u.F);
		}
}
void connect(pii a , pii b , int d)
{
	N[a.F][a.S].pb(mp(b , d));
	//cout << "(" << a.F << "," << a.S << ") -> (" << b.F << "," << b.S << ")\n";
}
int main()
{
	int n , m;cin >> n >> m;
	int b0 = -1;
	int b1 = -1;
	for(int i = 0; i < m ; i++)
	{
		int b , p;cin >> b >> p;
		pws[b].pb(p);
		if(i == 0)
			b0 = b;
		if(i == 1)
			b1 = b;
	}

	for(int i = 0; i < n ; i++)
	{
		dist[i][0] = INF;
		for(int j = 1; j <= Sq; j++)
		{
			dist[i][j] = INF;
			if(i >= j)
			{
				connect(mp(i , j) , mp(i - j , j) , 1);
				connect(mp(i - j , j) , mp(i , j) , 1);
				connect(mp(i , j) , mp(i , 0) , 0);
			}
		}
		sort(pws[i].begin() , pws[i].end());
		pws[i].resize(unique(pws[i].begin() , pws[i].end()) - pws[i].begin());

		for(int x : pws[i])
		{
			if(x <= Sq)
			{
				connect(mp(i , 0) , mp(i , x) , 0);
				connect(mp(i , x) , mp(i , 0) , 0);
			}
			else
			{
				for(int j = i - x , d = 1; j >= 0 ; j -= x , d++)
					connect(mp(i , 0) , mp(j , 0) , d);
				for(int j = i + x , d = 1; j < n ; j += x , d++)
					connect(mp(i , 0) , mp(j , 0) , d);
			}
		}
	}
	dist[b0][0] = 0;
	DFS(mp(b0 , 0));
	cout << dist[b1][0] << '\n';
}

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