Submission #554491

#	Time	Username	Problem	Language	Result	Execution time	Memory
554491		josanneo22	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	397 ms	6084 KiB

skyscraper

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
/*
void file_in(string s)
{
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
*/

void normal()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
    if (power == 0)
        return 1;
    ll result = ex(base, power / 2);
    if (power % 2 == 1)
        return(((result * result) % mod) * base) % mod;
    else return (result * result) % mod;
}

const int maxn = 30005;
int dist[maxn], B[maxn], P[maxn];
vi powers[maxn];
int n, m;

void solve(int s)
{
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(mp(dist[s]=0, s));// first is distance, second is position
    pii t;
    while (!q.empty())
    {
        t = q.top(); q.pop();
        if (t.f > dist[t.s]) continue;// we only need to find minimum distance, then if already greater than, no need to continue these values;
        trav(p, powers[t.s])//powers
        {
            for (int x = 1;t.s + p * x < n;++x)
            {
                if (dist[t.s + p * x] > t.f + x)
                {
                    q.push(mp(dist[t.s + p * x] = t.f + x, t.s + p * x));
                    if (binary_search(all(powers[t.s + p * x]), p)) break;//if there is a power there so no need to continue the other path
                }
            }
            for (int x = 1;t.s - p * x >= 0;++x)//duplicate but -p instead of +p
            {
                if (dist[t.s - p * x] > t.f + x)//note that distance always increases
                {
                    q.push(mp(dist[t.s - p * x] = t.f + x, t.s - p * x));
                    if (binary_search(all(powers[t.s - p * x]), p)) break;
                }
            }
        }
    }
}
int main()
{
    normal();

    cin >> n >> m;
    set<int> temp;
    FOR(i, 0, m)
    {
        cin >> B[i] >> P[i];
        powers[B[i]].pb(P[i]);
    }
    FOR(i, 0, n)
    {
        sort(all(powers[i]));
        powers[i].erase(unique(all(powers[i])), powers[i].end());//erase duplicates
    }
    fill(dist, dist + n, (int)1e9);
    solve(B[0]);
    if (dist[B[1]] == 1e9) cout << "-1";
    else cout << dist[B[1]];
    return 0;
}

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