oj.uz

Submission #25688

# Submission time Handle Problem Language Result Execution time Memory
25688 2017-06-23T14:55:51 Z gabrielsimoes Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 16 ms 50112 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,pii> plii;
const int MAXN = 3e4+10;
const int BLK = 200;

#define dist first
#define index second.first
#define delta second.second

int N, M, X, Y;
vector<pii> v[MAXN];
ll d[MAXN][BLK];
map<pii, bool> ok;
priority_queue<plii, vector<plii>, greater<plii>> q;

ll dBig[MAXN];
int posBig[MAXN];

inline void proc(int i, int dx, ll dd) {
	if (dx < BLK) {
		if (d[i][dx] == -1 || dd < d[i][dx]) {
			d[i][dx] = dd;
			q.push({dd, {i, dx}});
		}
	} else {
		if (dBig[i] == -1 || dd < dBig[i]) {
			dBig[i] = dd;
			q.push({dd, {i, dx}});
		}
	}
}

inline void procBig(int cur, int dx, ll d0) {
	// int cnt = cur/dx;
	// int i = cur - cnt*dx;
	// while (i < N) {
	// 	if (i != cur) proc(i, 0, d0 + abs(cnt));
	// 	i += dx; cnt--;
	// }

	int i = cur, cnt = 0;
	while ((i-=dx) >= 0) proc(i, 0, d0 + (++cnt));
	i = cur, cnt = 0;
	while ((i+=dx) < N) proc(i, 0, d0 + (++cnt));
}

inline void procSmall(int cur, int dx, ll d0) {
	if (cur - dx >= 0) {
		proc(cur-dx, dx, d0+1);
		proc(cur-dx, 0, d0+1);
	}

	if (cur + dx < N) {
		proc(cur+dx, dx, d0+1);
		proc(cur+dx, 0, d0+1);	
	}
}

inline void proc0(int ix) {
	for (pii p : v[ix])
		proc(p.first<BLK?ix:p.second, p.first, d[ix][0]);
}
 
void dijkstra() {
	memset(d, -1, sizeof(d));
	d[X][0] = 0; q.push({0,{X,0}});
	
	while (!q.empty()) {
		plii p = q.top(); q.pop();
		if (p.delta < BLK && d[p.index][p.delta] < p.dist) continue;
		if (p.delta >= BLK && dBig[p.index] < p.dist) continue;

		if (p.delta == 0) proc0(p.index);
		else if (p.delta < BLK) procSmall(p.index, p.delta, p.dist);
		else procBig(posBig[p.index], p.delta, p.dist);
	}
}
 
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0,a,b; i < M; i++) {
		scanf("%d %d", &a, &b);

		if (i == 0) X = a;
		else if (i == 1) Y = a;

		if (b != 0) v[a].push_back(pii(b,i));
		posBig[i] = a;
	}
	
	for (int i = 0; i < N; i++)
		sort(v[i].begin(), v[i].end()),
		v[i].resize(unique(v[i].begin(), v[i].end()) - v[i].begin());
 
	dijkstra();
	printf("%lld\n", d[Y][0]);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
skyscraper.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49972 KB Output is correct
2 Correct 3 ms 49972 KB Output is correct
3 Correct 3 ms 49972 KB Output is correct
4 Correct 6 ms 49972 KB Output is correct
5 Correct 3 ms 49972 KB Output is correct
6 Correct 0 ms 49972 KB Output is correct
7 Correct 3 ms 49972 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49972 KB Output is correct
2 Correct 0 ms 49972 KB Output is correct
3 Correct 3 ms 49972 KB Output is correct
4 Correct 3 ms 49972 KB Output is correct
5 Correct 3 ms 49972 KB Output is correct
6 Correct 0 ms 49972 KB Output is correct
7 Correct 13 ms 49972 KB Output is correct
8 Correct 3 ms 49972 KB Output is correct
9 Correct 3 ms 49972 KB Output is correct
10 Correct 16 ms 49972 KB Output is correct
11 Correct 3 ms 50108 KB Output is correct
12 Correct 6 ms 49972 KB Output is correct
13 Correct 9 ms 49972 KB Output is correct
14 Correct 0 ms 50108 KB Output is correct
15 Correct 3 ms 50108 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49972 KB Output is correct
2 Correct 0 ms 49972 KB Output is correct
3 Correct 3 ms 49972 KB Output is correct
4 Correct 0 ms 49972 KB Output is correct
5 Correct 6 ms 49972 KB Output is correct
6 Correct 3 ms 49972 KB Output is correct
7 Correct 3 ms 49972 KB Output is correct
8 Correct 0 ms 49972 KB Output is correct
9 Correct 0 ms 49972 KB Output is correct
10 Correct 0 ms 49972 KB Output is correct
11 Correct 0 ms 50108 KB Output is correct
12 Correct 6 ms 49972 KB Output is correct
13 Correct 3 ms 49972 KB Output is correct
14 Correct 13 ms 50108 KB Output is correct
15 Correct 6 ms 50108 KB Output is correct
16 Correct 3 ms 49972 KB Output is correct
17 Incorrect 3 ms 50112 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49972 KB Output is correct
2 Correct 0 ms 49972 KB Output is correct
3 Correct 0 ms 49972 KB Output is correct
4 Correct 3 ms 49972 KB Output is correct
5 Correct 0 ms 49972 KB Output is correct
6 Correct 9 ms 49972 KB Output is correct
7 Correct 6 ms 49972 KB Output is correct
8 Correct 0 ms 49972 KB Output is correct
9 Correct 0 ms 49972 KB Output is correct
10 Correct 3 ms 49972 KB Output is correct
11 Correct 6 ms 50108 KB Output is correct
12 Correct 9 ms 49972 KB Output is correct
13 Correct 6 ms 49972 KB Output is correct
14 Correct 3 ms 50108 KB Output is correct
15 Correct 3 ms 50108 KB Output is correct
16 Correct 0 ms 49972 KB Output is correct
17 Incorrect 3 ms 50112 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49972 KB Output is correct
2 Correct 0 ms 49972 KB Output is correct
3 Correct 6 ms 49972 KB Output is correct
4 Correct 0 ms 49972 KB Output is correct
5 Correct 3 ms 49972 KB Output is correct
6 Correct 0 ms 49972 KB Output is correct
7 Correct 3 ms 49972 KB Output is correct
8 Correct 6 ms 49972 KB Output is correct
9 Correct 3 ms 49972 KB Output is correct
10 Correct 0 ms 49972 KB Output is correct
11 Correct 0 ms 50108 KB Output is correct
12 Correct 3 ms 49972 KB Output is correct
13 Correct 0 ms 49972 KB Output is correct
14 Correct 6 ms 50108 KB Output is correct
15 Correct 6 ms 50108 KB Output is correct
16 Correct 3 ms 49972 KB Output is correct
17 Incorrect 6 ms 50112 KB Output isn't correct
18 Halted 0 ms 0 KB -