답안 #32891 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32891	2017-10-16T21:02:28 Z	minimario	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	813 ms	262144 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

#define f first
#define s second

const int MAX = 30005;
const int SQRT = 175;
const int INF = 1000000000;
int p[MAX], len[MAX]; // position, length

vector<pair<pii, int> > g[MAX][SQRT];
vector<int> powers[MAX]; // powers of doges at a given position

int dist[MAX][SQRT];

priority_queue<pair<int, pair<int, int> > > pq;
int ct = 0;
void dijk(int i, int j) {
	dist[i][j] = 0;
	//cout << i << " " << j << " " << 0 << endl;
	pq.push({0, {i, j}});
	while (!pq.empty()) {
		auto top = pq.top(); pq.pop();
		ct++;
		int d = -top.f;
		pair<int, int> loc = top.s;
		if (d > dist[loc.f][loc.s]) {
			continue; 
		}
		//cout << loc.f << " " << loc.s << endl;
		for (auto i : g[loc.f][loc.s]) {
			//cout << i.f.f << " " << i.f.s << endl;
			int d_new = (d + i.s);
			if (d_new < dist[i.f.f][i.f.s]) {
				dist[i.f.f][i.f.s] = d_new;
				//cout << "came from: " << loc.f << " " << loc.s << endl;
				//cout << i.f.f << " " << i.f.s << " " << d_new << endl;

				pq.push({-d_new, i.f});

			}
		}

	}
}
int main() {
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	for (int i=0; i<MAX; i++) {
		for (int j=0; j<SQRT; j++) {
			dist[i][j] = INF; 
		}
	}

	int n, m; scanf("%d %d", &n, &m);
	for (int i=0; i<m; i++) {
		scanf("%d %d", &p[i], &len[i]);
		powers[p[i]].push_back(len[i]);
	}

	for (int i=0; i<n; i++) {
		for (int j=1; j<SQRT; j++) {
			g[i][j].push_back({{i, 0}, 0});
		}
		for (int j : powers[i]) {
			if (j < SQRT) {
				g[i][0].push_back({{i, j}, 0});
			}
		}
	}
	for (int i=0; i<m; i++) {
		if (len[i] > SQRT) {

			for (int j=p[i]+len[i]; j<n; j+=len[i]) {
				g[p[i]][0].push_back({{j, 0}, (j-i)/len[i]});
			}
			for (int j=p[i]-len[i]; j>=0; j-=len[i]) {
				g[p[i]][0].push_back({{j, 0}, (i-j)/len[i]});
			}
		}
	}

	for (int i=0; i<n; i++) {
		for (int j=1; j<SQRT; j++) {
			if (i-j >= 0) { g[i][j].push_back({{i-j, j}, 1}); }
			if (i+j < n) { g[i][j].push_back({{i+j, j}, 1}); }
		}
		/*
		if (p[i] - len[i] >= 0) {
			g[p[i]][len[i]].push_back({{p[i]-len[i], len[i]}, 1});
		}
		if (p[i] + len[i] < n) {
			g[p[i]][len[i]].push_back({{p[i]+len[i], len[i]}, 1});
		}
		*/
	}


	dijk(p[0], 0);
	if (dist[p[1]][0] == INF) { printf("%d\n", -1); }
	else { printf("%d\n", dist[p[1]][len[1]]); }
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d %d", &n, &m);
                                  ^
skyscraper.cpp:61:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p[i], &len[i]);
                                 ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	146536 KB	Output is correct
2	Correct	43 ms	146536 KB	Output is correct
3	Correct	46 ms	146536 KB	Output is correct
4	Correct	33 ms	146536 KB	Output is correct
5	Correct	29 ms	146668 KB	Output is correct
6	Correct	49 ms	146668 KB	Output is correct
7	Correct	39 ms	146668 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	146536 KB	Output is correct
2	Correct	39 ms	146536 KB	Output is correct
3	Correct	43 ms	146536 KB	Output is correct
4	Correct	43 ms	146536 KB	Output is correct
5	Correct	39 ms	146668 KB	Output is correct
6	Correct	33 ms	146668 KB	Output is correct
7	Correct	36 ms	146668 KB	Output is correct
8	Correct	53 ms	146800 KB	Output is correct
9	Correct	36 ms	146932 KB	Output is correct
10	Correct	39 ms	147196 KB	Output is correct
11	Correct	39 ms	147328 KB	Output is correct
12	Correct	56 ms	147328 KB	Output is correct
13	Correct	43 ms	147348 KB	Output is correct
14	Correct	43 ms	147328 KB	Output is correct
15	Correct	39 ms	147328 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	146536 KB	Output is correct
2	Correct	29 ms	146536 KB	Output is correct
3	Correct	36 ms	146536 KB	Output is correct
4	Correct	33 ms	146536 KB	Output is correct
5	Correct	39 ms	146668 KB	Output is correct
6	Correct	36 ms	146668 KB	Output is correct
7	Correct	36 ms	146668 KB	Output is correct
8	Correct	29 ms	146800 KB	Output is correct
9	Correct	39 ms	146932 KB	Output is correct
10	Correct	39 ms	147196 KB	Output is correct
11	Correct	46 ms	147328 KB	Output is correct
12	Correct	39 ms	147328 KB	Output is correct
13	Correct	46 ms	147348 KB	Output is correct
14	Correct	36 ms	147328 KB	Output is correct
15	Correct	36 ms	147328 KB	Output is correct
16	Correct	29 ms	147988 KB	Output is correct
17	Memory limit exceeded	796 ms	262144 KB	Memory limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	146536 KB	Output is correct
2	Correct	43 ms	146536 KB	Output is correct
3	Correct	29 ms	146536 KB	Output is correct
4	Correct	39 ms	146536 KB	Output is correct
5	Correct	43 ms	146668 KB	Output is correct
6	Correct	36 ms	146668 KB	Output is correct
7	Correct	36 ms	146668 KB	Output is correct
8	Correct	36 ms	146800 KB	Output is correct
9	Correct	36 ms	146932 KB	Output is correct
10	Correct	26 ms	147196 KB	Output is correct
11	Correct	49 ms	147328 KB	Output is correct
12	Correct	43 ms	147328 KB	Output is correct
13	Correct	46 ms	147348 KB	Output is correct
14	Correct	43 ms	147328 KB	Output is correct
15	Correct	49 ms	147328 KB	Output is correct
16	Correct	23 ms	147988 KB	Output is correct
17	Memory limit exceeded	813 ms	262144 KB	Memory limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	146536 KB	Output is correct
2	Correct	49 ms	146536 KB	Output is correct
3	Correct	33 ms	146536 KB	Output is correct
4	Correct	29 ms	146536 KB	Output is correct
5	Correct	29 ms	146668 KB	Output is correct
6	Correct	36 ms	146668 KB	Output is correct
7	Correct	39 ms	146668 KB	Output is correct
8	Correct	39 ms	146800 KB	Output is correct
9	Correct	36 ms	146932 KB	Output is correct
10	Correct	29 ms	147196 KB	Output is correct
11	Correct	33 ms	147328 KB	Output is correct
12	Correct	33 ms	147328 KB	Output is correct
13	Correct	39 ms	147348 KB	Output is correct
14	Correct	26 ms	147328 KB	Output is correct
15	Correct	39 ms	147328 KB	Output is correct
16	Correct	39 ms	147988 KB	Output is correct
17	Memory limit exceeded	793 ms	262144 KB	Memory limit exceeded
18	Halted	0 ms	0 KB	-

답안 #32891

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0