oj.uz

Submission #695135

# Submission time Handle Problem Language Result Execution time Memory
695135 2023-02-04T18:33:18 Z Cyber_Wolf Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 742 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//Jakarta Skyscraper

const lg N  = 300005;

lg dist[N], in_queue[N];
vector<set<pair<lg, lg>>> adj(N);
vector<lg> b(N), p(N);

void dijkstra(lg src)
{
	priority_queue<array<lg, 2>> pq;
	pq.push({0, src});
	in_queue[src] = 1;
	memset(dist, 0x3f, sizeof(dist));
	dist[src] = 0;
	while(pq.size())
	{
		lg x = pq.top()[1];
		in_queue[x] = 0;
		pq.pop();
		for(auto [it, c] : adj[x])
		{
			if(dist[it] > dist[x]+c)
			{
				dist[it] = dist[x]+c;
				if(!in_queue[it])	pq.push({-dist[it], it});
				in_queue[it] = true;
			}
		}
	}
	return;
}


int main()
{
	fastio;
	lg n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> b[i] >> p[i];
	} 
	map<array<lg, 2>, lg> mp;
	for(int i = 0; i < m; i++)
	{
		lg x = b[i]+p[i], z = 1;
		while(x < n)
		{
			if(!mp.count({b[i], x}))
			{
				adj[b[i]].insert({x, z});	
				mp[{b[i], x}] = z;
			}
			else if(mp[{b[i], x}] > z)
			{
				adj[b[i]].insert({x, z});
				adj[b[i]].erase(adj[b[i]].find({x, mp[{b[i], x}]}));
				mp[{b[i], x}] = z;
			}
			z++;
			x += p[i];
		}
		x = b[i]-p[i];
		z = 1;
		while(x >= 0)
		{
			if(!mp.count({b[i], x}))
			{
				adj[b[i]].insert({x, z});	
				mp[{b[i], x}] = z;
			}
			else if(mp[{b[i], x}] > z)
			{
				adj[b[i]].insert({x, z});
				adj[b[i]].erase(adj[b[i]].find({x, mp[{b[i], x}]}));
				mp[{b[i], x}] = z;
			}
			z++;
			x -= p[i];
		}
	}
	dijkstra(b[0]);
	if(dist[b[1]] == dist[N-1])
	{
		cout << "-1\n";
		return 0;
	}
	cout << dist[b[1]] << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 11 ms 21412 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21460 KB Output is correct
7 Correct 12 ms 21588 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 13 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21460 KB Output is correct
7 Correct 10 ms 21364 KB Output is correct
8 Correct 11 ms 21432 KB Output is correct
9 Correct 10 ms 21460 KB Output is correct
10 Correct 13 ms 21596 KB Output is correct
11 Correct 14 ms 22100 KB Output is correct
12 Correct 24 ms 21476 KB Output is correct
13 Correct 32 ms 22604 KB Output is correct
14 Correct 13 ms 21716 KB Output is correct
15 Correct 12 ms 21716 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21460 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 10 ms 21472 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 12 ms 21588 KB Output is correct
11 Correct 14 ms 22100 KB Output is correct
12 Correct 26 ms 21528 KB Output is correct
13 Correct 32 ms 22684 KB Output is correct
14 Correct 12 ms 21716 KB Output is correct
15 Correct 12 ms 21752 KB Output is correct
16 Correct 14 ms 21972 KB Output is correct
17 Correct 19 ms 23912 KB Output is correct
18 Correct 12 ms 22100 KB Output is correct
19 Correct 12 ms 21964 KB Output is correct
20 Runtime error 728 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21448 KB Output is correct
2 Correct 10 ms 21440 KB Output is correct
3 Correct 10 ms 21452 KB Output is correct
4 Correct 11 ms 21460 KB Output is correct
5 Correct 12 ms 21460 KB Output is correct
6 Correct 10 ms 21392 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 10 ms 21448 KB Output is correct
10 Correct 12 ms 21588 KB Output is correct
11 Correct 14 ms 22060 KB Output is correct
12 Correct 28 ms 21464 KB Output is correct
13 Correct 32 ms 22592 KB Output is correct
14 Correct 12 ms 21716 KB Output is correct
15 Correct 12 ms 21744 KB Output is correct
16 Correct 12 ms 22008 KB Output is correct
17 Correct 19 ms 24028 KB Output is correct
18 Correct 12 ms 22100 KB Output is correct
19 Correct 14 ms 21972 KB Output is correct
20 Runtime error 742 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21372 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 13 ms 21460 KB Output is correct
4 Correct 13 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21460 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 11 ms 21460 KB Output is correct
9 Correct 10 ms 21460 KB Output is correct
10 Correct 13 ms 21588 KB Output is correct
11 Correct 13 ms 22100 KB Output is correct
12 Correct 24 ms 21472 KB Output is correct
13 Correct 32 ms 22680 KB Output is correct
14 Correct 12 ms 21696 KB Output is correct
15 Correct 12 ms 21688 KB Output is correct
16 Correct 12 ms 21972 KB Output is correct
17 Correct 19 ms 24020 KB Output is correct
18 Correct 12 ms 22100 KB Output is correct
19 Correct 14 ms 21972 KB Output is correct
20 Runtime error 740 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -