Submission #1275826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275826		_broken_	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1095 ms	9976 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define int short
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc (id << 1)
#define rc ((id << 1) ^ 1)

using namespace std;

const long long mod = 1e9 + 7, maxn = 3e4 + 9, base = 1e6 + 7;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 

int n,m,d[maxn];
vector<pair<int,int>> dog;

int32_t main()
{
	fast_io;
	cin >> n >> m;
	unordered_set<int> baghi;
	for(int i = 1; i <= m;i++)
	{
		int bi,pi;
		cin >> bi >>pi;
		dog.push_back({bi + 1 , pi});
		baghi.insert(i-1);
	}

	priority_queue< pair<int,int> , vector < pair<int,int>> ,greater<pair<int,int>> > q;
	q.push({ 0 , 0});
	bitset<maxn> mark;
	while (q.size())
	{
		pair<int, int> aa = q.top();	
		q.pop();
		if(mark[aa.second]) continue;
		d[aa.second] = aa.first;
		mark[aa.second] = true;
		baghi.erase(aa.second);
		int v = aa.second;
		if(baghi.size())
		for(int i : baghi)
			if((dog[i].first % dog[v].second) == (dog[v].first % dog[v].second))
				if(!mark[i])
					q.push({d[v] + (abs(dog[i].first - dog[v].first) / dog[v].second) , i});
		if(mark[1])
			break;
	}
	
	if(mark[1])
		cout << d[1] << "\n";
	else
		cout << "-1\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43