oj.uz

Submission #531129

# Submission time Handle Problem Language Result Execution time Memory
531129 2022-02-27T19:43:52 Z Hanksburger Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 123 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[21000005];
int dist[21000005], a[30005][175];
deque<int> deq;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, s, t, sz;
	cin >> n >> m;
	sz=n;
	for (int i=0; i<m; i++)
	{
		int b, p;
		cin >> b >> p;
		if (i==0)
			s=b;
		else if (i==1)
			t=b;
		if (p*p<=m)
		{
			if (!a[b][p])
			{
				a[b%p][p]=sz;
				sz++;
				adj[a[b%p][p]].push_back({b%p, 0});
				for (int j=b%p+p; j<n; j+=p)
				{
					a[j][p]=sz;
					sz++;
					adj[a[j][p]].push_back({j, 0});
					adj[a[j][p]].push_back({a[j-p][p], 1});
					adj[a[j-p][p]].push_back({a[j][p], 1});
				}
			}
			adj[b].push_back({a[b][p], 0});
		}
		else
		{
			int prev=b;
			for (int j=b-p; j>=0; j-=p)
			{
				adj[prev].push_back({sz, 1});
				adj[sz].push_back({j, 0});
				prev=sz;
				sz++;
			}
			prev=b;
			for (int j=b+p; j<n; j+=p)
			{
				adj[prev].push_back({sz, 1});
				adj[sz].push_back({j, 0});
				prev=sz;
				sz++;
			}
		}
	}
	for (int i=0; i<sz; i++)
		dist[i]=1e9;
	dist[s]=0;
	deq.push_back(s);
	while (!deq.empty())
	{
		int u=deq.front();
		deq.pop_front();
		for (int i=0; i<adj[u].size(); i++)
		{
			int v=adj[u][i].first, w=adj[u][i].second;
			if (dist[v]==1e9)
			{
				dist[v]=dist[u]+w;
				if (w)
					deq.push_back(v);
				else
					deq.push_front(v);
			}
		}
	}
	if (dist[t]==1e9)
		cout << -1;
	else
		cout << dist[t];
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i=0; i<adj[u].size(); i++)
      |                 ~^~~~~~~~~~~~~~
skyscraper.cpp:81:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |  if (dist[t]==1e9)
      |      ~~~~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 98 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 118 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -