oj.uz

Submission #45377

# Submission time Handle Problem Language Result Execution time Memory
45377 2018-04-13T05:03:07 Z JohnTitor Jakarta Skyscrapers (APIO15_skyscraper) C++11
100 / 100
 824 ms 35464 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1784 KB Output is correct
3 Correct 3 ms 1836 KB Output is correct
4 Correct 4 ms 1836 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 3 ms 1964 KB Output is correct
7 Correct 3 ms 1968 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1972 KB Output is correct
2 Correct 3 ms 2100 KB Output is correct
3 Correct 4 ms 2112 KB Output is correct
4 Correct 4 ms 2112 KB Output is correct
5 Correct 3 ms 2112 KB Output is correct
6 Correct 4 ms 2112 KB Output is correct
7 Correct 4 ms 2112 KB Output is correct
8 Correct 3 ms 2112 KB Output is correct
9 Correct 3 ms 2112 KB Output is correct
10 Correct 3 ms 2112 KB Output is correct
11 Correct 4 ms 2232 KB Output is correct
12 Correct 4 ms 2344 KB Output is correct
13 Correct 3 ms 2344 KB Output is correct
14 Correct 4 ms 2344 KB Output is correct
15 Correct 4 ms 2344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2344 KB Output is correct
2 Correct 3 ms 2344 KB Output is correct
3 Correct 5 ms 2344 KB Output is correct
4 Correct 3 ms 2344 KB Output is correct
5 Correct 4 ms 2344 KB Output is correct
6 Correct 4 ms 2344 KB Output is correct
7 Correct 3 ms 2344 KB Output is correct
8 Correct 3 ms 2344 KB Output is correct
9 Correct 3 ms 2344 KB Output is correct
10 Correct 3 ms 2368 KB Output is correct
11 Correct 4 ms 2408 KB Output is correct
12 Correct 3 ms 2436 KB Output is correct
13 Correct 3 ms 2436 KB Output is correct
14 Correct 5 ms 2476 KB Output is correct
15 Correct 4 ms 2492 KB Output is correct
16 Correct 3 ms 2500 KB Output is correct
17 Correct 5 ms 2892 KB Output is correct
18 Correct 4 ms 3548 KB Output is correct
19 Correct 4 ms 3816 KB Output is correct
20 Correct 12 ms 3824 KB Output is correct
21 Correct 4 ms 3824 KB Output is correct
22 Correct 5 ms 3824 KB Output is correct
23 Correct 4 ms 3824 KB Output is correct
24 Correct 5 ms 3824 KB Output is correct
25 Correct 5 ms 3892 KB Output is correct
26 Correct 4 ms 3928 KB Output is correct
27 Correct 5 ms 3940 KB Output is correct
28 Correct 6 ms 3960 KB Output is correct
29 Correct 8 ms 3980 KB Output is correct
30 Correct 5 ms 3980 KB Output is correct
31 Correct 6 ms 3992 KB Output is correct
32 Correct 6 ms 3996 KB Output is correct
33 Correct 14 ms 4000 KB Output is correct
34 Correct 14 ms 4012 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4012 KB Output is correct
2 Correct 3 ms 4012 KB Output is correct
3 Correct 3 ms 4012 KB Output is correct
4 Correct 3 ms 4012 KB Output is correct
5 Correct 3 ms 4012 KB Output is correct
6 Correct 3 ms 4012 KB Output is correct
7 Correct 3 ms 4012 KB Output is correct
8 Correct 4 ms 4012 KB Output is correct
9 Correct 3 ms 4012 KB Output is correct
10 Correct 3 ms 4012 KB Output is correct
11 Correct 4 ms 4012 KB Output is correct
12 Correct 3 ms 4012 KB Output is correct
13 Correct 3 ms 4012 KB Output is correct
14 Correct 4 ms 4012 KB Output is correct
15 Correct 4 ms 4012 KB Output is correct
16 Correct 4 ms 4012 KB Output is correct
17 Correct 6 ms 4012 KB Output is correct
18 Correct 5 ms 4012 KB Output is correct
19 Correct 5 ms 4016 KB Output is correct
20 Correct 6 ms 4152 KB Output is correct
21 Correct 4 ms 4152 KB Output is correct
22 Correct 4 ms 4152 KB Output is correct
23 Correct 4 ms 4152 KB Output is correct
24 Correct 6 ms 4152 KB Output is correct
25 Correct 5 ms 4224 KB Output is correct
26 Correct 5 ms 4244 KB Output is correct
27 Correct 6 ms 4260 KB Output is correct
28 Correct 6 ms 4280 KB Output is correct
29 Correct 9 ms 4296 KB Output is correct
30 Correct 7 ms 4296 KB Output is correct
31 Correct 9 ms 4312 KB Output is correct
32 Correct 8 ms 4312 KB Output is correct
33 Correct 15 ms 4316 KB Output is correct
34 Correct 14 ms 4328 KB Output is correct
35 Correct 16 ms 4724 KB Output is correct
36 Correct 6 ms 4724 KB Output is correct
37 Correct 19 ms 5112 KB Output is correct
38 Correct 19 ms 5656 KB Output is correct
39 Correct 20 ms 5920 KB Output is correct
40 Correct 19 ms 6184 KB Output is correct
41 Correct 19 ms 6448 KB Output is correct
42 Correct 7 ms 6460 KB Output is correct
43 Correct 9 ms 6664 KB Output is correct
44 Correct 10 ms 6872 KB Output is correct
45 Correct 49 ms 7528 KB Output is correct
46 Correct 41 ms 7792 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7792 KB Output is correct
2 Correct 3 ms 7792 KB Output is correct
3 Correct 3 ms 7792 KB Output is correct
4 Correct 3 ms 7792 KB Output is correct
5 Correct 3 ms 7792 KB Output is correct
6 Correct 3 ms 7792 KB Output is correct
7 Correct 3 ms 7792 KB Output is correct
8 Correct 4 ms 7792 KB Output is correct
9 Correct 3 ms 7792 KB Output is correct
10 Correct 4 ms 7792 KB Output is correct
11 Correct 4 ms 7792 KB Output is correct
12 Correct 3 ms 7792 KB Output is correct
13 Correct 3 ms 7792 KB Output is correct
14 Correct 5 ms 7792 KB Output is correct
15 Correct 4 ms 7792 KB Output is correct
16 Correct 3 ms 7792 KB Output is correct
17 Correct 5 ms 7792 KB Output is correct
18 Correct 4 ms 7792 KB Output is correct
19 Correct 5 ms 7792 KB Output is correct
20 Correct 4 ms 7792 KB Output is correct
21 Correct 3 ms 7792 KB Output is correct
22 Correct 4 ms 7792 KB Output is correct
23 Correct 5 ms 7792 KB Output is correct
24 Correct 7 ms 7792 KB Output is correct
25 Correct 5 ms 7792 KB Output is correct
26 Correct 5 ms 7792 KB Output is correct
27 Correct 4 ms 7792 KB Output is correct
28 Correct 5 ms 7792 KB Output is correct
29 Correct 10 ms 7792 KB Output is correct
30 Correct 7 ms 7792 KB Output is correct
31 Correct 9 ms 7792 KB Output is correct
32 Correct 7 ms 7792 KB Output is correct
33 Correct 13 ms 7792 KB Output is correct
34 Correct 14 ms 7792 KB Output is correct
35 Correct 15 ms 7792 KB Output is correct
36 Correct 6 ms 7792 KB Output is correct
37 Correct 25 ms 8056 KB Output is correct
38 Correct 23 ms 8524 KB Output is correct
39 Correct 30 ms 8788 KB Output is correct
40 Correct 20 ms 9152 KB Output is correct
41 Correct 19 ms 9284 KB Output is correct
42 Correct 7 ms 9328 KB Output is correct
43 Correct 7 ms 9532 KB Output is correct
44 Correct 7 ms 9708 KB Output is correct
45 Correct 43 ms 10476 KB Output is correct
46 Correct 60 ms 10624 KB Output is correct
47 Correct 92 ms 18136 KB Output is correct
48 Correct 21 ms 25348 KB Output is correct
49 Correct 22 ms 27124 KB Output is correct
50 Correct 26 ms 28892 KB Output is correct
51 Correct 89 ms 31504 KB Output is correct
52 Correct 84 ms 31884 KB Output is correct
53 Correct 37 ms 31884 KB Output is correct
54 Correct 26 ms 31884 KB Output is correct
55 Correct 24 ms 31884 KB Output is correct
56 Correct 35 ms 32248 KB Output is correct
57 Correct 100 ms 32248 KB Output is correct
58 Correct 31 ms 32248 KB Output is correct
59 Correct 42 ms 32248 KB Output is correct
60 Correct 43 ms 32248 KB Output is correct
61 Correct 37 ms 32580 KB Output is correct
62 Correct 72 ms 33468 KB Output is correct
63 Correct 74 ms 34556 KB Output is correct
64 Correct 68 ms 34908 KB Output is correct
65 Correct 296 ms 35012 KB Output is correct
66 Correct 799 ms 35236 KB Output is correct
67 Correct 824 ms 35464 KB Output is correct