oj.uz

Submission #110208

# Submission time Handle Problem Language Result Execution time Memory
110208 2019-05-10T07:47:01 Z hugo_pm Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 17 ms 7424 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

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

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borneSuj = 30*1000 + 5;
const int borneTab = 10*borneSuj;
int gt[borneSuj][200];
int arr = -1;

int nbPlaces, nbDoges, nbNoeuds;
int limSqd;

vector<pii> adj[borneTab];

void solve()
{
	cin >> nbPlaces >> nbDoges;
	nbNoeuds = nbPlaces;
	limSqd = sqrt(nbPlaces);
	if (limSqd+1 < nbPlaces) ++limSqd;

	form2(distance, 1, limSqd) {
		form(ini, distance) {
			for (int place = ini; place < nbPlaces; place += distance) {
				int corNod = nbNoeuds; ++nbNoeuds;
				adj[corNod].push_back({place, 0});
				gt[place][distance] = corNod;

				if (place != ini) {
					adj[corNod].push_back({corNod-1, 1});
					adj[corNod-1].push_back({corNod, 1});
				}
			}
		}
	}

	form(iDoge, nbDoges) {
		int pos, saut;
		cin >> pos >> saut;
		if (iDoge == 1) arr = pos;
		if (saut < limSqd) {
			adj[pos].push_back({gt[pos][saut], 0});
		} else {
			for (int dd = 1; pos + dd*saut < nbPlaces; ++dd) {
				adj[pos].push_back({pos+dd*saut, dd});
			}

			for (int dd = 1; pos - dd*saut >= 0; ++dd) {
				adj[pos].push_back({pos - dd*saut, dd});
			}
		}
	}

	vector<int> md(nbNoeuds, BIG);
	md[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0,0});
	while (! pq.empty()) {
		int dis = pq.top().fi, nod = pq.top().se;
		pq.pop();
		if (dis != md[nod]) continue;

		if (nod == arr) { cout << dis << "\n"; return; }

		for (auto voRaw : adj[nod]) {
			int vo = voRaw.fi, poids = voRaw.se;
			if (dis + poids < md[vo]) {
				md[vo] = dis+poids;
				pq.push({md[vo], vo});
			}
		}
	}

	cout << "-1\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -