Submission #1102567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102567		Ali_BBN	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	938 ms	70044 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define mp make_pair
#define ll long long
#define migmig cin.tie(NULL);ios_base::sync_with_stdio(false)
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define fi first
#define sec second
#define endl "\n"
#define pii pair <int, int>
using namespace std;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll INF18 = 1e18;
const int MAXN = 3e4 + 1;
const int LOG = 23;
vector <int> all[MAXN];
map <pii, int> shit;
set <pii> s;
bool be[MAXN];
vector <pii> adj[MAXN];
ll dist[MAXN];
int now = 0;
int t0, t1;
int ft = 0;
bool flag = 0;
void dijk(int r){
    min_heap(pii) pq;
    dist[r] = 0;
    pq.push(mp(0, r));
    while (!pq.empty()){
		ft++;
        auto [d, v] = pq.top();
		if (v == t1) return;
        pq.pop();
        if (d == dist[v]){
            for (auto [u, w] : adj[v]){
                if (dist[u] > d + w){
                    dist[u] = d + w;
                    pq.push(mp(d + w, u));
                }
            }
        }
    }
}
void solve(){
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int b, p;
		cin >> b >> p;
		if (i == 0) t0 = b;
		if (i == 1) t1 = b;
		if (s.find(mp(b % p, p)) == s.end()) shit[mp(b % p, p)] = now++, s.insert(mp(b % p, p));
		be[b] = 1;
		all[shit[mp(b % p, p)]].pb(b);
	}
	vector <int> v;
	for (auto i : s){
		v.clear();
		int t = shit[i];
		for (int j : all[t]) v.pb(j);
		sort(v.begin(), v.end());
		int last = i.fi;
		for (int j = 0; j < v.size(); j++){
			for (int k = last; k < v[j]; k += i.sec){
				if (be[k]) adj[v[j]].pb(mp(k, (v[j] - k) / i.sec));
			}
			for (int k = v[j] + i.sec; k < n; k += i.sec){
				if (be[k]) adj[v[j]].pb(mp(k, (k - v[j]) / i.sec));
				if (j != v.size() - 1 && k == v[j + 1]) break;
			}
			last = v[j];
		}
	}
	fill(dist, dist + n, INF);
	dijk(t0);
	if (dist[t1] == INF) cout << -1 << endl;
	else cout << dist[t1] << endl;
}
int main(){
	migmig;
	int tc = 1;
	// cin >> tc;
	for (int ti = 0; ti < tc; ti++) solve();
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijk(int)':
skyscraper.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         auto [d, v] = pq.top();
      |              ^
skyscraper.cpp:40:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             for (auto [u, w] : adj[v]){
      |                       ^
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j = 0; j < v.size(); j++){
      |                   ~~^~~~~~~~~~
skyscraper.cpp:74:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if (j != v.size() - 1 && k == v[j + 1]) break;
      |         ~~^~~~~~~~~~~~~~~

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