oj.uz

답안 #695131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695131 2023-02-04T18:31:40 Z Cyber_Wolf Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 33 ms 22684 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, z}));
				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, z}));
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 9 ms 21460 KB Output is correct
4 Correct 9 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21456 KB Output is correct
7 Correct 10 ms 21388 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 21460 KB Output is correct
2 Correct 9 ms 21432 KB Output is correct
3 Correct 9 ms 21460 KB Output is correct
4 Correct 9 ms 21368 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 14 ms 21380 KB Output is correct
8 Correct 10 ms 21404 KB Output is correct
9 Correct 12 ms 21460 KB Output is correct
10 Correct 10 ms 21588 KB Output is correct
11 Correct 13 ms 22004 KB Output is correct
12 Correct 26 ms 21472 KB Output is correct
13 Correct 33 ms 22624 KB Output is correct
14 Correct 11 ms 21716 KB Output is correct
15 Incorrect 11 ms 21716 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 21460 KB Output is correct
2 Correct 12 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 21376 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 11 ms 21448 KB Output is correct
8 Correct 10 ms 21392 KB Output is correct
9 Correct 11 ms 21448 KB Output is correct
10 Correct 10 ms 21588 KB Output is correct
11 Correct 13 ms 22100 KB Output is correct
12 Correct 24 ms 21468 KB Output is correct
13 Correct 33 ms 22684 KB Output is correct
14 Correct 14 ms 21664 KB Output is correct
15 Incorrect 13 ms 21716 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 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 11 ms 21452 KB Output is correct
5 Correct 13 ms 21444 KB Output is correct
6 Correct 10 ms 21460 KB Output is correct
7 Correct 10 ms 21372 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 11 ms 21588 KB Output is correct
11 Correct 14 ms 22100 KB Output is correct
12 Correct 25 ms 21472 KB Output is correct
13 Correct 33 ms 22680 KB Output is correct
14 Correct 12 ms 21716 KB Output is correct
15 Incorrect 12 ms 21716 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 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 12 ms 21432 KB Output is correct
9 Correct 13 ms 21436 KB Output is correct
10 Correct 11 ms 21588 KB Output is correct
11 Correct 14 ms 22100 KB Output is correct
12 Correct 24 ms 21460 KB Output is correct
13 Correct 32 ms 22588 KB Output is correct
14 Correct 12 ms 21716 KB Output is correct
15 Incorrect 14 ms 21680 KB Output isn't correct
16 Halted 0 ms 0 KB -