oj.uz

Submission #17334

# Submission time Handle Problem Language Result Execution time Memory
17334 2015-11-22T02:40:41 Z comet Jakarta Skyscrapers (APIO15_skyscraper) C++
0 / 100
 0 ms 1956 KB 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back


int N,M;
int a[30010],P[30010];
int dist[30010];
bool chk[30010];

priority_queue<pp,vector<pp>,greater<pp> > Q;

mat doge;

int main(){
	freopen(".in","r",stdin);

	scanf("%d%d",&N,&M);
	doge.assign(N,vec());
	for(int i=0;i<M;i++){
		scanf("%d%d",&a[i],&P[i]);
		doge[a[i]].push_back(P[i]);
	}

	memset(dist,0x3f,sizeof(dist));
	int INF=dist[0];
	dist[a[0]]=0;
	Q.push(pp(0,a[0]));

	int v;
	while(!Q.empty()){
		do{
			v=Q.top().second;Q.pop();
		}while(!Q.empty()&&chk[v]);
		chk[v]=1;
		if(v==a[1])break;
		for(int k=0;k<doge[v].size();k++){
			int p=doge[v][k];
			for(int i=v+p;i<N;i+=p){
				if(dist[i]>dist[v]+abs(v-i)/p){
					dist[i]=dist[v]+abs(v-i)/p;
					Q.push(pp(dist[i],i));
				}
			}
			for(int i=v-p;i>=0;i-=p){
				if(dist[i]>dist[v]+abs(v-i)/p){
					dist[i]=dist[v]+abs(v-i)/p;
					Q.push(pp(dist[i],i));
				}
			}
		}
	}

	if(dist[a[1]]==INF){
		puts("-1");
	}else{
		printf("%d",dist[a[1]]);
	}

}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1956 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1956 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1956 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1956 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1956 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -