oj.uz

Submission #488564

# Submission time Handle Problem Language Result Execution time Memory
488564 2021-11-19T16:29:12 Z pooyashams Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 91 ms 197732 KB 
#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int maxn = 3e4+10;
const int mxsq = 210;
const int maxt = maxn*mxsq;
const ll inf = 1e16;

int len[maxn];
int pos[maxn];
ll dist[maxt];
vector<pli> G[maxt];

inline void add_edge(int a, int b, ll w, bool nd)
{
	G[a].push_back({w, b});
	if(nd)
		G[b].push_back({w, a});
}

inline void dijkstra(int s)
{
	set<pli> pq;
	fill(dist, dist+maxt, inf);
	auto mark = [&](int v, ll d)
	{
		if(dist[v] <= d) return;
		pq.erase({dist[v], v});
		dist[v] = d;
		pq.insert({dist[v], v});
	};
	mark(s, 0);
	while(!pq.empty())
	{
		int t = pq.begin()->second;
		ll d = pq.begin()->first;
		pq.erase(pq.begin());
		for(pli e: G[t])
		{
			int u = e.second;
			ll w = e.first;
			mark(u, d+w);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> m >> n;
	const int sq = sqrt(n);
	for(int p = 0; p < sq; p++)
	{
		for(int i = 0; i < m; i++)
		{
			if(i + p < m)
				add_edge(p*m+i, p*m+i+p, 1, true);
			add_edge(p*m+i, i, 0, false);
		}
	}
	for(int i = 0; i < n; i++)
	{
		cin >> pos[i] >> len[i];
		int b = pos[i];
		int p = len[i];
		if(p >= sq)
		{
			for(int j = b%p; j < m; j += p)
				add_edge(b, j, abs(b-j)/p, false);
		}
		else
		{
			add_edge(b, p*m+b, 0, false);
		}
	}
	dijkstra(0);
	cout << dist[1] << endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 197560 KB Output is correct
2 Incorrect 87 ms 197572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 197596 KB Output is correct
2 Incorrect 87 ms 197596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 197732 KB Output is correct
2 Incorrect 86 ms 197568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 197572 KB Output is correct
2 Incorrect 87 ms 197544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 197576 KB Output is correct
2 Incorrect 86 ms 197556 KB Output isn't correct
3 Halted 0 ms 0 KB -