oj.uz

Submission #459419

# Submission time Handle Problem Language Result Execution time Memory
459419 2021-08-08T13:16:03 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 844 ms 177528 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=2500000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N, M;
vector <pii> BP;
vector <pair<int, bool>> adj[mxM];
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;
        for(auto nxt : adj[now])
        {
            if(dis[nxt.fir]>dis[now]+nxt.sec)
            {
                dis[nxt.fir]=dis[now]+nxt.sec;
                if(dis[now]==dis[nxt.fir])   lst.push_front(nxt.fir);
                else    lst.push_back(nxt.fir);
            }
        }
    }
}
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);
    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)
            {
                adj[j].push_back({idx, 0});
                while(cur<M && BP[cur].fir==j && BP[cur].sec==BP[ncur].sec)   cur++;
            }
            adj[idx].push_back({j, 0});
            if(!jog)    jog=true;
            else
            {
                adj[idx].push_back({idx-1, 1});
                adj[idx-1].push_back({idx, 1});
            }
            idx++;
            if(idx>=mxM)    return 0;
        }
    }
    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 33 ms 58956 KB Output is correct
2 Correct 33 ms 59008 KB Output is correct
3 Correct 33 ms 58924 KB Output is correct
4 Correct 36 ms 58936 KB Output is correct
5 Correct 36 ms 59036 KB Output is correct
6 Correct 33 ms 58896 KB Output is correct
7 Correct 33 ms 58956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59012 KB Output is correct
2 Correct 33 ms 58924 KB Output is correct
3 Correct 33 ms 59092 KB Output is correct
4 Correct 35 ms 59012 KB Output is correct
5 Correct 35 ms 59056 KB Output is correct
6 Correct 33 ms 58956 KB Output is correct
7 Correct 34 ms 59020 KB Output is correct
8 Correct 33 ms 58992 KB Output is correct
9 Correct 33 ms 59044 KB Output is correct
10 Correct 35 ms 59028 KB Output is correct
11 Correct 37 ms 59192 KB Output is correct
12 Correct 38 ms 58956 KB Output is correct
13 Correct 34 ms 59020 KB Output is correct
14 Correct 37 ms 59364 KB Output is correct
15 Correct 40 ms 59340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 58988 KB Output is correct
2 Correct 34 ms 58956 KB Output is correct
3 Correct 34 ms 58948 KB Output is correct
4 Correct 32 ms 58948 KB Output is correct
5 Correct 33 ms 59020 KB Output is correct
6 Correct 33 ms 59028 KB Output is correct
7 Correct 34 ms 59008 KB Output is correct
8 Correct 34 ms 58968 KB Output is correct
9 Correct 34 ms 59152 KB Output is correct
10 Correct 33 ms 59120 KB Output is correct
11 Correct 35 ms 59240 KB Output is correct
12 Correct 35 ms 59068 KB Output is correct
13 Correct 35 ms 59056 KB Output is correct
14 Correct 35 ms 59332 KB Output is correct
15 Correct 35 ms 59332 KB Output is correct
16 Correct 35 ms 59156 KB Output is correct
17 Correct 36 ms 59728 KB Output is correct
18 Correct 34 ms 59332 KB Output is correct
19 Correct 33 ms 59212 KB Output is correct
20 Correct 34 ms 59228 KB Output is correct
21 Correct 33 ms 59148 KB Output is correct
22 Correct 34 ms 59252 KB Output is correct
23 Correct 35 ms 59388 KB Output is correct
24 Correct 36 ms 59628 KB Output is correct
25 Correct 35 ms 59372 KB Output is correct
26 Correct 35 ms 59332 KB Output is correct
27 Correct 36 ms 59348 KB Output is correct
28 Correct 37 ms 60228 KB Output is correct
29 Correct 52 ms 62212 KB Output is correct
30 Correct 35 ms 59852 KB Output is correct
31 Correct 40 ms 60652 KB Output is correct
32 Correct 38 ms 60252 KB Output is correct
33 Correct 57 ms 65284 KB Output is correct
34 Correct 60 ms 65276 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 58900 KB Output is correct
2 Correct 32 ms 58948 KB Output is correct
3 Correct 32 ms 59036 KB Output is correct
4 Correct 34 ms 58924 KB Output is correct
5 Correct 34 ms 59016 KB Output is correct
6 Correct 33 ms 58948 KB Output is correct
7 Correct 32 ms 58980 KB Output is correct
8 Correct 35 ms 59076 KB Output is correct
9 Correct 33 ms 59064 KB Output is correct
10 Correct 34 ms 59048 KB Output is correct
11 Correct 34 ms 59276 KB Output is correct
12 Correct 34 ms 59060 KB Output is correct
13 Correct 33 ms 58956 KB Output is correct
14 Correct 36 ms 59360 KB Output is correct
15 Correct 35 ms 59340 KB Output is correct
16 Correct 34 ms 59184 KB Output is correct
17 Correct 35 ms 59768 KB Output is correct
18 Correct 33 ms 59288 KB Output is correct
19 Correct 34 ms 59244 KB Output is correct
20 Correct 34 ms 59212 KB Output is correct
21 Correct 34 ms 59148 KB Output is correct
22 Correct 34 ms 59232 KB Output is correct
23 Correct 35 ms 59316 KB Output is correct
24 Correct 36 ms 59672 KB Output is correct
25 Correct 39 ms 59332 KB Output is correct
26 Correct 34 ms 59528 KB Output is correct
27 Correct 35 ms 59332 KB Output is correct
28 Correct 39 ms 60240 KB Output is correct
29 Correct 46 ms 62164 KB Output is correct
30 Correct 37 ms 59852 KB Output is correct
31 Correct 39 ms 60736 KB Output is correct
32 Correct 37 ms 60228 KB Output is correct
33 Correct 58 ms 65284 KB Output is correct
34 Correct 58 ms 65284 KB Output is correct
35 Correct 65 ms 64780 KB Output is correct
36 Correct 37 ms 59924 KB Output is correct
37 Correct 90 ms 68564 KB Output is correct
38 Correct 90 ms 68000 KB Output is correct
39 Correct 86 ms 67916 KB Output is correct
40 Correct 87 ms 67904 KB Output is correct
41 Correct 88 ms 67908 KB Output is correct
42 Correct 48 ms 59560 KB Output is correct
43 Correct 45 ms 59528 KB Output is correct
44 Correct 44 ms 59408 KB Output is correct
45 Correct 201 ms 84476 KB Output is correct
46 Correct 211 ms 84564 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 59012 KB Output is correct
2 Correct 32 ms 58964 KB Output is correct
3 Correct 34 ms 58992 KB Output is correct
4 Correct 34 ms 58960 KB Output is correct
5 Correct 32 ms 58956 KB Output is correct
6 Correct 32 ms 58968 KB Output is correct
7 Correct 32 ms 58928 KB Output is correct
8 Correct 32 ms 59020 KB Output is correct
9 Correct 34 ms 59004 KB Output is correct
10 Correct 33 ms 59024 KB Output is correct
11 Correct 34 ms 59280 KB Output is correct
12 Correct 34 ms 58968 KB Output is correct
13 Correct 35 ms 59000 KB Output is correct
14 Correct 35 ms 59332 KB Output is correct
15 Correct 35 ms 59468 KB Output is correct
16 Correct 34 ms 59148 KB Output is correct
17 Correct 36 ms 59716 KB Output is correct
18 Correct 36 ms 59312 KB Output is correct
19 Correct 35 ms 59212 KB Output is correct
20 Correct 34 ms 59172 KB Output is correct
21 Correct 37 ms 59092 KB Output is correct
22 Correct 34 ms 59220 KB Output is correct
23 Correct 33 ms 59356 KB Output is correct
24 Correct 37 ms 59756 KB Output is correct
25 Correct 35 ms 59400 KB Output is correct
26 Correct 35 ms 59436 KB Output is correct
27 Correct 40 ms 59328 KB Output is correct
28 Correct 37 ms 60212 KB Output is correct
29 Correct 45 ms 62160 KB Output is correct
30 Correct 36 ms 59852 KB Output is correct
31 Correct 39 ms 60760 KB Output is correct
32 Correct 37 ms 60160 KB Output is correct
33 Correct 61 ms 65288 KB Output is correct
34 Correct 60 ms 65196 KB Output is correct
35 Correct 67 ms 64752 KB Output is correct
36 Correct 39 ms 59900 KB Output is correct
37 Correct 90 ms 68532 KB Output is correct
38 Correct 104 ms 67908 KB Output is correct
39 Correct 95 ms 67956 KB Output is correct
40 Correct 86 ms 67904 KB Output is correct
41 Correct 94 ms 67880 KB Output is correct
42 Correct 44 ms 59596 KB Output is correct
43 Correct 45 ms 59568 KB Output is correct
44 Correct 44 ms 59332 KB Output is correct
45 Correct 206 ms 84516 KB Output is correct
46 Correct 200 ms 84512 KB Output is correct
47 Correct 283 ms 98188 KB Output is correct
48 Correct 70 ms 71092 KB Output is correct
49 Correct 60 ms 66496 KB Output is correct
50 Correct 69 ms 66472 KB Output is correct
51 Correct 128 ms 75764 KB Output is correct
52 Correct 136 ms 77336 KB Output is correct
53 Correct 63 ms 64152 KB Output is correct
54 Correct 38 ms 60620 KB Output is correct
55 Correct 45 ms 61960 KB Output is correct
56 Correct 56 ms 61868 KB Output is correct
57 Correct 150 ms 81684 KB Output is correct
58 Correct 53 ms 62872 KB Output is correct
59 Correct 64 ms 64312 KB Output is correct
60 Correct 72 ms 65800 KB Output is correct
61 Correct 65 ms 64980 KB Output is correct
62 Correct 131 ms 85188 KB Output is correct
63 Correct 844 ms 177528 KB Output is correct
64 Incorrect 356 ms 174776 KB Output isn't correct
65 Halted 0 ms 0 KB -