oj.uz

Submission #389747

# Submission time Handle Problem Language Result Execution time Memory
389747 2021-04-14T12:42:17 Z milleniumEeee Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 113 ms 149776 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

const int MAXN = 30005;
const int SHIFT = 50000;
const int S = 175;
const int INF = 1e9;

int pos[MAXN], p[MAXN];
int n, m;

struct node {
	int v, pw, cost;
	node () {
		
	}
	node (int v_, int pw_, int cost_) {
		v = v_;
		pw = pw_;
		cost = cost_;
	}
};

struct Compare_node {
	bool operator () (node const &p1, node const &p2) {
		if (p1.cost != p2.cost) {
			return p1.cost < p2.cost;			
		}
		if (p1.v != p2.v) {
			return p1.v < p2.v;
		}
		return p1.pw < p2.pw;
	}
};

vector <int> big[MAXN];
vector <int> small[MAXN];
vector <node> g[MAXN][S];
int dist[MAXN][S];

bool in(int pos) {
	return 0 <= pos && pos < n;
}

signed main() {
	fastInp;
	cin >> n >> m;
	set <int> all_small;
	for (int i = 0; i < m; i++) {
		cin >> pos[i] >> p[i];
		if (p[i] >= S) {
			big[pos[i]].pb(p[i]);
		} else {
			small[pos[i]].pb(p[i]);
			all_small.insert(p[i]);
		}
	}
	// node -> v pw cost
	for (int i = 0; i < n; i++) {
		for (int val : all_small) {
			if (in(i - val)) {
				g[i][val].pb(node(i - val, val, 1));
			}
			if (in(i + val)) {
				g[i][val].pb(node(i + val, val, 1));
			}
		}
		sort(all(small[i]));
		small[i].erase(unique(all(small[i])), small[i].end());
		for (int val : small[i]) {
			g[i][0].pb(node(i, val, 0));
		}
	}
	set <node, Compare_node> pq;
	vector <bool> used(MAXN, false);
	memset(dist, -1, sizeof(dist));
	pq.insert(node(pos[0], 0, 0));
	dist[pos[0]][0] = 0;
	
	auto ers = [&](int v, int pw) {
		//auto it = pq.lower_bound(node(v, pw, -INF));
		//if (it != pq.end() && it->v == v && it->pw == pw) {
			//pq.erase(it);
		//}
	};
	
	while (!pq.empty()) {
		int v = pq.begin()->v;
		int pw = pq.begin()->pw;
		int cost = pq.begin()->cost;
		pq.erase(pq.begin());
		if (cost > dist[v][pw]) {
			continue;
		}
		if (!used[v]) { // впервые добрались до v
			used[v] = 1;
			for (int el : big[v]) {
				for (int to = v % el; to < n; to += el) {
					int c = abs(v - to) / el;
					if (dist[to][0] == -1 || dist[to][0] > cost + c) {
						dist[to][0] = cost + c;
						ers(to, 0);
						pq.insert(node(to, 0, -dist[to][0]));
					}
				}
			}
		}
		// change our pw
		if (dist[v][0] == -1 || dist[v][0] > dist[v][pw]) {
			dist[v][0] = dist[v][pw];
			ers(v, 0);
			pq.insert(node(v, 0, -dist[v][pw]));
		}
		for (auto el : g[v][pw]) {
			int new_v = el.v;
			int new_pw = el.pw;			
			int c = el.cost;
			if (dist[new_v][new_pw] == -1 || dist[new_v][new_pw] > dist[v][pw] + c) {
				dist[new_v][new_pw] = dist[v][pw] + c;
				ers(new_v, new_pw);
				pq.insert(node(new_v, new_pw, -dist[new_v][new_pw]));
			}
		}
	}
	cout << dist[pos[1]][0] << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 145520 KB Output is correct
2 Correct 80 ms 145512 KB Output is correct
3 Correct 81 ms 145524 KB Output is correct
4 Correct 92 ms 145552 KB Output is correct
5 Correct 82 ms 145508 KB Output is correct
6 Correct 80 ms 145460 KB Output is correct
7 Correct 82 ms 145476 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 145564 KB Output is correct
2 Correct 89 ms 145556 KB Output is correct
3 Correct 83 ms 145548 KB Output is correct
4 Correct 80 ms 145516 KB Output is correct
5 Correct 81 ms 145516 KB Output is correct
6 Correct 81 ms 145532 KB Output is correct
7 Correct 79 ms 145580 KB Output is correct
8 Correct 81 ms 145480 KB Output is correct
9 Correct 81 ms 145608 KB Output is correct
10 Correct 89 ms 145748 KB Output is correct
11 Correct 110 ms 145860 KB Output is correct
12 Correct 81 ms 145732 KB Output is correct
13 Correct 82 ms 145604 KB Output is correct
14 Correct 87 ms 145732 KB Output is correct
15 Correct 90 ms 145732 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 145556 KB Output is correct
2 Correct 81 ms 145480 KB Output is correct
3 Correct 82 ms 145540 KB Output is correct
4 Correct 82 ms 145464 KB Output is correct
5 Correct 82 ms 145484 KB Output is correct
6 Correct 79 ms 145476 KB Output is correct
7 Correct 80 ms 145540 KB Output is correct
8 Correct 82 ms 145528 KB Output is correct
9 Correct 83 ms 145620 KB Output is correct
10 Correct 89 ms 145736 KB Output is correct
11 Correct 109 ms 145808 KB Output is correct
12 Correct 82 ms 145680 KB Output is correct
13 Correct 81 ms 145592 KB Output is correct
14 Correct 88 ms 145748 KB Output is correct
15 Correct 88 ms 145744 KB Output is correct
16 Correct 84 ms 146432 KB Output is correct
17 Incorrect 97 ms 149776 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 145732 KB Output is correct
2 Correct 83 ms 145484 KB Output is correct
3 Correct 83 ms 145576 KB Output is correct
4 Correct 83 ms 145480 KB Output is correct
5 Correct 79 ms 145496 KB Output is correct
6 Correct 82 ms 145532 KB Output is correct
7 Correct 81 ms 145488 KB Output is correct
8 Correct 80 ms 145468 KB Output is correct
9 Correct 90 ms 145616 KB Output is correct
10 Correct 95 ms 145860 KB Output is correct
11 Correct 110 ms 145792 KB Output is correct
12 Correct 82 ms 145664 KB Output is correct
13 Correct 80 ms 145600 KB Output is correct
14 Correct 88 ms 145740 KB Output is correct
15 Correct 87 ms 145840 KB Output is correct
16 Correct 84 ms 146396 KB Output is correct
17 Incorrect 100 ms 149768 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 145556 KB Output is correct
2 Correct 82 ms 145448 KB Output is correct
3 Correct 82 ms 145476 KB Output is correct
4 Correct 81 ms 145572 KB Output is correct
5 Correct 84 ms 145548 KB Output is correct
6 Correct 86 ms 145492 KB Output is correct
7 Correct 94 ms 145496 KB Output is correct
8 Correct 80 ms 145516 KB Output is correct
9 Correct 81 ms 145600 KB Output is correct
10 Correct 91 ms 145836 KB Output is correct
11 Correct 113 ms 145832 KB Output is correct
12 Correct 82 ms 145604 KB Output is correct
13 Correct 80 ms 145580 KB Output is correct
14 Correct 88 ms 145844 KB Output is correct
15 Correct 92 ms 145776 KB Output is correct
16 Correct 91 ms 146500 KB Output is correct
17 Incorrect 97 ms 149728 KB Output isn't correct
18 Halted 0 ms 0 KB -