Submission #111088

#	Time	Username	Problem	Language	Result	Execution time	Memory
111088		aleksam	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1066 ms	2600 KiB

skyscraper

//Jakarta skysrcapers
#include <bits/stdc++.h>
#define INF MOD
#define MOD 100000007
#define MAX_N 30005
#define MAX_M 30005
#define K 0.95
int mg;

using namespace std;

int N, M;
int source, dest;
struct edge{
	int d, w;
};
vector<int> soli[MAX_N];
int dist[MAX_N];
bool mark[MAX_N];
clock_t t;
bool legal;
void dijkstra(int s){
	if(clock()-t>K*CLOCKS_PER_SEC){legal=0;return;}
	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;
		mark[v]=1;
		if(v==dest)return;
		int d=soli[v].size();
		for(int j=0; j<d; ++j){
			int p=soli[v][j];
			int sk=v-p;
			while(sk>=0 && sk>v-mg*p){
				int w=(v-sk)/p;
				if(!mark[sk] && dist[sk]>dist[v]+w && soli[sk].size()>0){
					dist[sk]=dist[v]+w;
					pq.emplace(-1*(dist[v]+w), sk);
				}
				sk-=p;
			}
			sk=v+p;
			while(sk<N && sk<v+mg*p){
				int w=(sk-v)/p;
				if(!mark[sk] && dist[sk]>dist[v]+w && soli[sk].size()>0){
					dist[sk]=dist[v]+w;
					pq.emplace(-1*(dist[v]+w), sk);
				}
				sk+=p;
			}
		}
		if(clock()-t>K*CLOCKS_PER_SEC){legal=0;return;}
	}
}
inline bool cmp(int i, int j){return i>j;}
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);
	}
	t=clock();
	for(int i=0; i<N; ++i){
		sort(soli[i].begin(), soli[i].end(), cmp);
	}
	
	mg=2500;
	legal=1;
	dijkstra(source);
	int output=dist[dest]>100000000?-1:dist[dest];
	mg=30000;
	if(legal)
	dijkstra(source);
	if(!legal){cout<<output;return 0;}
	if(dist[dest]>100000000)cout<<"-1"<<endl;
	else 
	cout<<dist[dest];
	return 0;
}

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

5 6 
0 1 1
1 2 2 
2 3 1 
1 3 4
0 4 2
4 3 1
0 3


3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
*/

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