oj.uz

Submission #459442

# Submission time Handle Problem Language Result Execution time Memory
459442 2021-08-08T13:40:52 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 93604 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=30010;
const int mxM=7300000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N, M;
vector <pii> BP;
int l[mxM], r[mxM];
short in[mxM];
vector <int> out[mxN];
int idx;
int X, Y;
list <int> lst;
int dis[mxM];
bool Chk[mxM];
bool cmp1(pii a, pii b)
{
    if(a.sec!=b.sec) return a.sec<b.sec;
    if(a.fir%a.sec!=b.fir%b.sec)    return a.fir%a.sec<b.fir%b.sec;
    return a.fir<b.fir;
}
void zero_one_bfs()
{
    while(!lst.empty())
    {
        int now=lst.front();
        lst.pop_front();
        if(Chk[now])    continue;
        Chk[now]=true;
        if(now<N)
        {
            for(int nxt : out[now])
            {
                if(dis[nxt]>dis[now])
                {
                    dis[nxt]=dis[now];
                    lst.push_front(nxt);
                }
            }
        }
        else
        {
            if(l[now]!=-1)
            {
                if(dis[l[now]]>dis[now]+1)
                {
                    dis[l[now]]=dis[now]+1;
                    lst.push_back(l[now]);
                }
            }
            if(r[now]!=-1)
            {
                if(dis[r[now]]>dis[now]+1)
                {
                    dis[r[now]]=dis[now]+1;
                    lst.push_back(r[now]);
                }
            }
            if(dis[in[now]]>dis[now])
            {
                dis[in[now]]=dis[now];
                lst.push_front(in[now]);
            }
        }
    }
}
int main()
{
    gibon
    cin >> N >> M;
    idx=N;
    BP.resize(M);
    for(int i=0;i<M;i++)
    {
        cin >> BP[i].fir >> BP[i].sec;
        if(i==0)    X=BP[i].fir;
        if(i==1)    Y=BP[i].fir;
    }
    sort(BP.begin(), BP.end(), cmp1);
    for(int i=0;i<mxM;i++)  l[i]=r[i]=in[i]=-1;
    int cur=0;
    while(cur<M)
    {
        int ncur=cur;
        bool jog=false;
        for(int j=BP[ncur].fir%BP[ncur].sec;j<N;j+=BP[ncur].sec)
        {
            if(cur<M && BP[cur].fir==j && BP[cur].sec==BP[ncur].sec)
            {
                out[j].push_back(idx);
                while(cur<M && BP[cur].fir==j && BP[cur].sec==BP[ncur].sec)   cur++;
            }
            in[idx]=j;
            if(!jog)    jog=true;
            else
            {
                l[idx]=idx-1;
                r[idx-1]=idx;
            }
            idx++;
        }
    }
    for(int i=0;i<idx;i++)
    {
        dis[i]=MOD;
    }
    dis[X]=0;
    lst.push_front(X);
    zero_one_bfs();
    if(dis[Y]==MOD) cout << -1;
    else    cout << dis[Y];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 72396 KB Output is correct
2 Correct 33 ms 72396 KB Output is correct
3 Correct 31 ms 72408 KB Output is correct
4 Correct 32 ms 72404 KB Output is correct
5 Correct 33 ms 72428 KB Output is correct
6 Correct 35 ms 72392 KB Output is correct
7 Correct 36 ms 72408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 72380 KB Output is correct
2 Correct 30 ms 72316 KB Output is correct
3 Correct 36 ms 72412 KB Output is correct
4 Correct 32 ms 72340 KB Output is correct
5 Correct 33 ms 72356 KB Output is correct
6 Correct 37 ms 72348 KB Output is correct
7 Correct 41 ms 72396 KB Output is correct
8 Correct 30 ms 72396 KB Output is correct
9 Correct 31 ms 72456 KB Output is correct
10 Correct 36 ms 72436 KB Output is correct
11 Correct 34 ms 72512 KB Output is correct
12 Correct 42 ms 72412 KB Output is correct
13 Correct 34 ms 72424 KB Output is correct
14 Correct 36 ms 72444 KB Output is correct
15 Correct 31 ms 72556 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 72348 KB Output is correct
2 Correct 39 ms 72412 KB Output is correct
3 Correct 37 ms 72448 KB Output is correct
4 Correct 35 ms 72448 KB Output is correct
5 Correct 35 ms 72416 KB Output is correct
6 Correct 33 ms 72396 KB Output is correct
7 Correct 32 ms 72420 KB Output is correct
8 Correct 36 ms 72348 KB Output is correct
9 Correct 38 ms 72420 KB Output is correct
10 Correct 38 ms 72396 KB Output is correct
11 Correct 33 ms 72524 KB Output is correct
12 Correct 35 ms 72352 KB Output is correct
13 Correct 36 ms 72396 KB Output is correct
14 Correct 32 ms 72528 KB Output is correct
15 Correct 34 ms 72488 KB Output is correct
16 Correct 41 ms 72372 KB Output is correct
17 Correct 39 ms 72576 KB Output is correct
18 Correct 34 ms 72384 KB Output is correct
19 Correct 33 ms 72416 KB Output is correct
20 Correct 32 ms 72428 KB Output is correct
21 Correct 35 ms 72384 KB Output is correct
22 Correct 34 ms 72436 KB Output is correct
23 Correct 38 ms 72476 KB Output is correct
24 Correct 34 ms 72564 KB Output is correct
25 Correct 64 ms 72472 KB Output is correct
26 Correct 35 ms 72424 KB Output is correct
27 Correct 41 ms 72388 KB Output is correct
28 Correct 39 ms 72596 KB Output is correct
29 Correct 38 ms 72692 KB Output is correct
30 Correct 31 ms 72516 KB Output is correct
31 Correct 44 ms 72516 KB Output is correct
32 Correct 45 ms 72536 KB Output is correct
33 Correct 54 ms 73120 KB Output is correct
34 Correct 39 ms 73124 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 72396 KB Output is correct
2 Correct 38 ms 72380 KB Output is correct
3 Correct 39 ms 72336 KB Output is correct
4 Correct 33 ms 72356 KB Output is correct
5 Correct 34 ms 72364 KB Output is correct
6 Correct 38 ms 72424 KB Output is correct
7 Correct 42 ms 72316 KB Output is correct
8 Correct 32 ms 72376 KB Output is correct
9 Correct 32 ms 72332 KB Output is correct
10 Correct 31 ms 72396 KB Output is correct
11 Correct 32 ms 72452 KB Output is correct
12 Correct 32 ms 72360 KB Output is correct
13 Correct 31 ms 72376 KB Output is correct
14 Correct 32 ms 72536 KB Output is correct
15 Correct 32 ms 72524 KB Output is correct
16 Correct 34 ms 72448 KB Output is correct
17 Correct 40 ms 72600 KB Output is correct
18 Correct 34 ms 72500 KB Output is correct
19 Correct 39 ms 72468 KB Output is correct
20 Correct 33 ms 72524 KB Output is correct
21 Correct 31 ms 72364 KB Output is correct
22 Correct 33 ms 72388 KB Output is correct
23 Correct 50 ms 72492 KB Output is correct
24 Correct 34 ms 72484 KB Output is correct
25 Correct 35 ms 72520 KB Output is correct
26 Correct 34 ms 72436 KB Output is correct
27 Correct 33 ms 72388 KB Output is correct
28 Correct 32 ms 72516 KB Output is correct
29 Correct 33 ms 72724 KB Output is correct
30 Correct 33 ms 72544 KB Output is correct
31 Correct 67 ms 72644 KB Output is correct
32 Correct 39 ms 72516 KB Output is correct
33 Correct 43 ms 73028 KB Output is correct
34 Correct 41 ms 73124 KB Output is correct
35 Correct 53 ms 73808 KB Output is correct
36 Correct 38 ms 72592 KB Output is correct
37 Correct 50 ms 74308 KB Output is correct
38 Correct 63 ms 74436 KB Output is correct
39 Correct 58 ms 74408 KB Output is correct
40 Correct 58 ms 74384 KB Output is correct
41 Correct 105 ms 74468 KB Output is correct
42 Correct 43 ms 72696 KB Output is correct
43 Correct 48 ms 72696 KB Output is correct
44 Correct 43 ms 72644 KB Output is correct
45 Correct 152 ms 76140 KB Output is correct
46 Correct 87 ms 76144 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 72388 KB Output is correct
2 Correct 33 ms 72424 KB Output is correct
3 Correct 39 ms 72420 KB Output is correct
4 Correct 38 ms 72432 KB Output is correct
5 Correct 32 ms 72344 KB Output is correct
6 Correct 31 ms 72444 KB Output is correct
7 Correct 51 ms 72320 KB Output is correct
8 Correct 35 ms 72400 KB Output is correct
9 Correct 38 ms 72324 KB Output is correct
10 Correct 33 ms 72472 KB Output is correct
11 Correct 32 ms 72460 KB Output is correct
12 Correct 32 ms 72416 KB Output is correct
13 Correct 31 ms 72400 KB Output is correct
14 Correct 32 ms 72460 KB Output is correct
15 Correct 31 ms 72516 KB Output is correct
16 Correct 36 ms 72388 KB Output is correct
17 Correct 41 ms 72580 KB Output is correct
18 Correct 34 ms 72404 KB Output is correct
19 Correct 32 ms 72488 KB Output is correct
20 Correct 33 ms 72532 KB Output is correct
21 Correct 32 ms 72452 KB Output is correct
22 Correct 31 ms 72508 KB Output is correct
23 Correct 33 ms 72496 KB Output is correct
24 Correct 33 ms 72524 KB Output is correct
25 Correct 32 ms 72524 KB Output is correct
26 Correct 34 ms 72388 KB Output is correct
27 Correct 49 ms 72476 KB Output is correct
28 Correct 33 ms 72532 KB Output is correct
29 Correct 47 ms 72684 KB Output is correct
30 Correct 33 ms 72448 KB Output is correct
31 Correct 33 ms 72572 KB Output is correct
32 Correct 34 ms 72524 KB Output is correct
33 Correct 47 ms 73028 KB Output is correct
34 Correct 42 ms 73144 KB Output is correct
35 Correct 52 ms 73780 KB Output is correct
36 Correct 36 ms 72616 KB Output is correct
37 Correct 53 ms 74276 KB Output is correct
38 Correct 68 ms 74460 KB Output is correct
39 Correct 62 ms 74380 KB Output is correct
40 Correct 61 ms 74420 KB Output is correct
41 Correct 55 ms 74436 KB Output is correct
42 Correct 44 ms 72664 KB Output is correct
43 Correct 41 ms 72616 KB Output is correct
44 Correct 43 ms 72648 KB Output is correct
45 Correct 85 ms 76148 KB Output is correct
46 Correct 94 ms 76104 KB Output is correct
47 Correct 121 ms 77764 KB Output is correct
48 Correct 44 ms 74092 KB Output is correct
49 Correct 40 ms 73676 KB Output is correct
50 Correct 39 ms 73600 KB Output is correct
51 Correct 106 ms 75168 KB Output is correct
52 Correct 71 ms 75252 KB Output is correct
53 Correct 50 ms 73852 KB Output is correct
54 Correct 34 ms 72648 KB Output is correct
55 Correct 33 ms 72740 KB Output is correct
56 Correct 59 ms 73816 KB Output is correct
57 Correct 65 ms 74772 KB Output is correct
58 Correct 48 ms 73156 KB Output is correct
59 Correct 48 ms 73204 KB Output is correct
60 Correct 49 ms 73412 KB Output is correct
61 Correct 49 ms 73320 KB Output is correct
62 Correct 73 ms 76072 KB Output is correct
63 Correct 486 ms 84740 KB Output is correct
64 Correct 666 ms 87224 KB Output is correct
65 Execution timed out 1030 ms 93604 KB Time limit exceeded
66 Halted 0 ms 0 KB -