oj.uz

Submission #49172

# Submission time Handle Problem Language Result Execution time Memory
49172 2018-05-23T04:43:53 Z Namnamseo Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 210 ms 85116 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, m;
vector<int> b[30010];

const int Lim = 100;
const int V = 30000*(Lim + 1);

int dist[V];
vector<pp> edge[V];

vector<int> usable[30010];

int main()
{
	read(n, m);
	int tg = 0;
	for(int i=0; i<m; ++i){
		int b, p;
		read(b, p);
		if(i == 1) tg = b;
		
		if(p <= Lim) ::b[p].pb(b);
		else usable[b].pb(p);
	}
	
	for(int p=1; p<=Lim; ++p) if(b[p].size()){
		for(int a:b[p]) edge[a].eb(p*n+a, 0);
		for(int i=0; i<n; ++i){
			if(i+p < n) edge[p*n+i].eb(p*n+(i+p), 1);
			if(i-p >=0) edge[p*n+i].eb(p*n+(i-p), 1);
			edge[p*n+i].eb(i, 0);
		}
	}
	
	fill(dist+1, dist+V, 1e9);
	priority_queue<pp> pq;
	pq.emplace(0, 0);
	
	while(pq.size()){
		int md, x; tie(md, x) = pq.top(); pq.pop();
		md = -md;
		if(md != dist[x]) continue;
		
		auto relax = [&](int y, int d){
			if(dist[y] > d){
				dist[y] = d;
				pq.emplace(-d, y);
			}
		};
		for(auto et:edge[x]) relax(et.x, md+et.y);
		
		if(x < n){
			for(int p:usable[x]){
				for(int i=1;;++i) if(x-p*i>=0) relax(x-p*i, md+i); else break;
				for(int i=1;;++i) if(x+p*i<n) relax(x+p*i, md+i); else break;
			}
		}
	}
	
	int ans = dist[tg];
	if(ans == 1e9) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'void read(int&)':
skyscraper.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
skyscraper.cpp: In function 'void read(ll&)':
skyscraper.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 84728 KB Output is correct
2 Correct 77 ms 84840 KB Output is correct
3 Correct 77 ms 84840 KB Output is correct
4 Correct 73 ms 84840 KB Output is correct
5 Correct 72 ms 84840 KB Output is correct
6 Correct 77 ms 84988 KB Output is correct
7 Correct 76 ms 84988 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 84992 KB Output is correct
2 Correct 75 ms 84992 KB Output is correct
3 Correct 70 ms 84992 KB Output is correct
4 Correct 71 ms 84992 KB Output is correct
5 Correct 72 ms 84992 KB Output is correct
6 Correct 69 ms 85000 KB Output is correct
7 Correct 74 ms 85100 KB Output is correct
8 Incorrect 80 ms 85104 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 85104 KB Output is correct
2 Correct 76 ms 85104 KB Output is correct
3 Correct 74 ms 85104 KB Output is correct
4 Correct 68 ms 85104 KB Output is correct
5 Correct 77 ms 85104 KB Output is correct
6 Correct 75 ms 85104 KB Output is correct
7 Correct 74 ms 85104 KB Output is correct
8 Incorrect 76 ms 85116 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 85116 KB Output is correct
2 Correct 69 ms 85116 KB Output is correct
3 Correct 75 ms 85116 KB Output is correct
4 Correct 77 ms 85116 KB Output is correct
5 Correct 79 ms 85116 KB Output is correct
6 Correct 71 ms 85116 KB Output is correct
7 Correct 69 ms 85116 KB Output is correct
8 Incorrect 70 ms 85116 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 85116 KB Output is correct
2 Correct 78 ms 85116 KB Output is correct
3 Correct 77 ms 85116 KB Output is correct
4 Correct 77 ms 85116 KB Output is correct
5 Correct 77 ms 85116 KB Output is correct
6 Correct 84 ms 85116 KB Output is correct
7 Correct 210 ms 85116 KB Output is correct
8 Incorrect 76 ms 85116 KB Output isn't correct
9 Halted 0 ms 0 KB -