Submission #110985

#	Time	Username	Problem	Language	Result	Execution time	Memory
110985		aleksam	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	5 ms	1920 KiB

skyscraper

//Jakarta skysrcapers
#include <bits/stdc++.h>
#define INF MOD
#define MOD 100000007
#define MAX_N 30005
#define MAX_M 30005

using namespace std;

int N, M;
int source, dest;
struct edge{
	int d, w;
};
vector<int> soli[MAX_N];
vector<edge> adj[MAX_N];
int dist[MAX_N];
bool mark[MAX_N];

void dijkstra(int s){
	memset(dist, INF, sizeof(dist));
	memset(mark, 0, sizeof(mark));
	
	dist[s]=0;
	priority_queue<pair<int, int> > pq;
	pq.emplace(0, s);
	while(!pq.empty()){
		auto cur=pq.top();
		pq.pop();
		int v=cur.second;
		if(mark[v])continue;
		//printf("v=%d\n", v);
		mark[v]=1;
		dist[v]=cur.first;
		int d=adj[v].size();
		for(int i=0; i<d; ++i){
			int u=adj[v][i].d;
			if(!mark[u] && dist[u]>dist[v]+adj[v][i].w){
				dist[u]=dist[v]+adj[v][i].w;
				pq.emplace(dist[v]+adj[v][i].w, u);
			}
		}
	}
}

int main(){
	//ios::sync_with_stdio(false);
	cin>>N>>M;
	int b;
	cin>>source>>b;
	soli[source].push_back(b);
	cin>>dest>>b;
	soli[dest].push_back(b);
	for(int i=2; i<M; ++i){
		int p;
		cin>>b>>p;
		soli[b].push_back(p);
	}
	for(int i=0; i<N; ++i){
		int d=soli[i].size();
		for(int j=0; j<d; ++j){
			int p=soli[i][j];
			int sk=i-p;
			while(sk>=0){
				edge e;
				e.d=sk;
				e.w=(i-sk)/p;
				adj[i].push_back(e);
				sk-=p;
			}
			sk=i+p;
			while(sk<N){
				edge e;
				e.d=sk;
				e.w=(sk-i)/p;
				adj[i].push_back(e);
				sk+=p;
			}
		}
	}
	/*for(int i=0; i<N; ++i){
		int d=adj[i].size();
		printf("adj[%d]:", i);
		for(int j=0; j<d; ++j){
			printf("%d ", adj[i][j].d);
		}
		printf("\n");
	}*/
	dijkstra(source);
	cout<<dist[dest];
	return 0;
}

/*
5 3
0 2
1 1
4 1
*/

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