oj.uz

Submission #41513

# Submission time Handle Problem Language Result Execution time Memory
41513 2018-02-18T02:50:26 Z wzy Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 23 ms 21740 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
vector<pii> adj[300005];
int  n, m;
set<int> p[300005];
long long d[300005];

int main(){
	scanf("%d%d" ,  &n,  &m);
	for(int i = 0 ; i <m ; i ++){
		int  b, x;
		scanf("%d%d" , &b , &x);
		p[b].insert(x);
	}
	for(int i = 0 ; i < n; i++){
		for(auto t : p[i]){
			for(int j = 1  ; j*t + i < n ; j++){
				adj[i].pb(pii(j , j*t+i));
				if(p[j*t + i].count(t)) break;
			}
			for(int j = 1 ; i - j*t >=0 ; j++){
				adj[i].pb(pii(j , i-j*t));
				if(p[i - j*t].count(t)) break;

			}	
		}
	}
	priority_queue<pii , vector<pii> , greater<pii> > pq;
	pq.push(pii(0 , 0));
	for(int i = 0 ; i< n; i++) d[i] = (long long) 1e18;
	d[0] = 0;
	while(!pq.empty()){
		pii u = pq.top();
		pq.pop();
		if(d[u.S] != u.F) continue;
		d[u.S] = u.F;
		for(int i = 0 ; i < adj[u.S].size() ; i++){
			pii v = adj[u.S][i];
			if(d[v.S] > u.F + v.F){
				d[v.S] = u.F + v.F;
				pq.push(pii(u.F + v.F , v.S));
			}
		}
	}
	if(d[1] == (int) 1e18) puts("-1");
	else{
		printf("%lld\n" , d[1]);
	}
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[u.S].size() ; i++){
                     ^
skyscraper.cpp:14:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" ,  &n,  &m);
                          ^
skyscraper.cpp:17:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &b , &x);
                          ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21368 KB Output is correct
2 Correct 17 ms 21472 KB Output is correct
3 Incorrect 17 ms 21544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21560 KB Output is correct
2 Correct 18 ms 21612 KB Output is correct
3 Incorrect 18 ms 21612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21648 KB Output is correct
2 Correct 18 ms 21648 KB Output is correct
3 Incorrect 20 ms 21648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21720 KB Output is correct
2 Correct 18 ms 21720 KB Output is correct
3 Incorrect 18 ms 21740 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21740 KB Output is correct
2 Correct 23 ms 21740 KB Output is correct
3 Incorrect 18 ms 21740 KB Output isn't correct
4 Halted 0 ms 0 KB -