Submission #45377

#	Time	Username	Problem	Language	Result	Execution time	Memory
45377		JohnTitor	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	824 ms	35464 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Jakarta_Skyscrapers"
int n, m;
int b[30001];
int p[30001];
vector <int> big[30001];
vector <int> small[30001];
int f[30001][176];
int sq=175;
class data{
public:
    int u, s, d;
    data(){}
    data(int _u, int _s, int _d){
        u=_u;
        s=_s;
        d=_d;
    }
};
class cmp{
public:
    bool operator ()(data a, data b){
        return a.d>b.d;
    }
};
priority_queue <data, vector <data>, cmp> q;
const int inf=mask(30);
void dij(){
    FOR(i, 0, n) FOR(j, 0, sq) f[i][j]=inf;
    f[b[0]][0]=0;
    q.push(data(b[0], 0, 0));
    data t;
    while(!q.empty()){
        t=q.top();
        q.pop();
        if(t.d>f[t.u][t.s]) continue;
//        cerr<<t.u<<" "<<t.s<<" "<<t.d<<'\n';
        if(t.s){///can move
            if(t.u-t.s>=0){
                if(f[t.u-t.s][t.s]>t.d+1){
                    f[t.u-t.s][t.s]=t.d+1;
                    q.push(data(t.u-t.s, t.s, t.d+1));
                }
            }
            if(t.u+t.s<n){
                if(f[t.u+t.s][t.s]>t.d+1){
                    f[t.u+t.s][t.s]=t.d+1;
                    q.push(data(t.u+t.s, t.s, t.d+1));
                }
            }
            if(t.d<f[t.u][0]){
                f[t.u][0]=t.d;
                q.push(data(t.u, 0, t.d));
            }
        }
        else{
            ///move using small steps:
            for(int i: small[t.u]){
                if(f[t.u][p[i]]>f[t.u][0]){
                    f[t.u][p[i]]=f[t.u][0];
                    q.push(data(t.u, p[i], f[t.u][p[i]]));
                }
            }
            ///move using big steps:
            for(int i: big[t.u]){
                for(int x=b[i]%p[i]; x<=n; x+=p[i]){
                    if(f[x][0]>f[t.u][0]+abs(t.u-x)/p[i]){
                        f[x][0]=f[t.u][0]+abs(t.u-x)/p[i];
                        q.push(data(x, 0, f[x][0]));
                    }
                }
            }
        }
    }
}
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(n);
    read(m);
    FFOR(i, 0, m){
        read(b[i]);
        read(p[i]);
        if(p[i]<sq) small[b[i]].pb(i);
        else big[b[i]].pb(i);
    }
    dij();
    int ans=f[b[1]][0];
//    for(int x=b[1]%p[1]; x<n; x+=p[1]) ans=min(ans, f[x][0]+abs(b[1]-x)/p[1]);
    if(ans==inf) ans=-1;
    writeln(ans);
}

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