Submission #255956

#	Time	Username	Problem	Language	Result	Execution time	Memory
255956		Saacoota	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1095 ms	121328 KiB

skyscraper

#include    <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b)  for(int i=(a);i<(b);++i)
#define fi  first
#define se  second
#define LL  unsigned long long
#define uint unsigned int
#define pb  push_back
#define eb  emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "SKY"
using   namespace   std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int oo = 0x3f;
int n , m , p[30004] , b[30004];
vector < int > vc[30004];
int d[30004][505][2];
struct node {
    int dis , i , p , type;
};
bool operator > (node a , node b) {
    return a.dis > b.dis;
}
///--------------------------
void readf() {
    cin >> n >> m;
}
///--------------------------
void solve() {
    int sqr = 500;
    for (int i = 0 ; i < m ; ++i) {
        cin >> b[i] >> p[i];
        vc[b[i]].pb(i);
    }
    int ans = 1e9;
    memset(d,0x3f,sizeof(d));
    priority_queue < node , vector < node > , greater < node > > wyna;
    wyna.push({0 , b[0] , 0 , 0});
    d[b[0]][0][0] = 0;
    while (!wyna.empty()) {
        node x = wyna.top();
        int dis = x.dis , pk = x.p , type = x.type , i = x.i;
        if (i == b[1]) ans = min(ans , dis);
        wyna.pop();
        if (dis != d[i][pk][type]) continue;
        if (type == 0) {
            for (auto x : vc[i])
            if (p[x] <= sqr) {
                if (d[i][p[x]][1] > dis) {
                    d[i][p[x]][1] = dis;
                    wyna.push({dis , i , p[x] , 1});
                }
            } else {
                int pp = p[x];
                int cnt = 0;
                for (int x = i ; x < n ; x += pp)  {
                    if (d[x][0][0] > dis + cnt) {
                        d[x][0][0] = dis + cnt;
                        wyna.push({dis + cnt , x , 0 , 0});
                    }
                    cnt++;
                }
                cnt = 0;
                for (int x = i ; x >= 0 ; x -= pp) {
                    if (d[x][0][0] > dis + cnt) {
                        d[x][0][0] = dis + cnt;
                        wyna.push({dis + cnt , x , 0 , 0});
                    }
                    cnt++;
                }

            }
        }
        if (type == 1) {
            if (i + pk < n && d[i + pk][pk][1] > dis + 1) {
                d[i + pk][pk][1] = dis + 1;
                wyna.push({dis + 1 , i + pk , pk , 1});
            }
            if (i - pk >= 0 && d[i - pk][pk][1] > dis + 1) {
                d[i - pk][pk][1] = dis + 1;
                wyna.push({dis + 1 , i - pk , pk , 1});
            }
            if (d[i][0][0] > dis) {
                d[i][0][0] = dis;
                wyna.push({dis , i , 0 , 0});
            }
        }
    }
    if (ans == 1e9) cout << -1;
    else cout << ans;
}
///--------------------------
int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   solve();
}

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