oj.uz

Submission #459413

# Submission time Handle Problem Language Result Execution time Memory
459413 2021-08-08T13:09:38 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 216424 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=3000000;
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(lst.empty() || dis[lst.front()]>=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;
        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(j!=BP[ncur].fir%BP[ncur].sec)
            {
                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 40 ms 70720 KB Output is correct
2 Correct 41 ms 70656 KB Output is correct
3 Correct 40 ms 70732 KB Output is correct
4 Correct 40 ms 70656 KB Output is correct
5 Correct 43 ms 70676 KB Output is correct
6 Correct 41 ms 70732 KB Output is correct
7 Correct 39 ms 70636 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70752 KB Output is correct
2 Correct 40 ms 70768 KB Output is correct
3 Correct 39 ms 70652 KB Output is correct
4 Correct 40 ms 70732 KB Output is correct
5 Correct 41 ms 70640 KB Output is correct
6 Correct 40 ms 70680 KB Output is correct
7 Correct 40 ms 70712 KB Output is correct
8 Correct 40 ms 70732 KB Output is correct
9 Correct 45 ms 70716 KB Output is correct
10 Correct 43 ms 70760 KB Output is correct
11 Correct 41 ms 70980 KB Output is correct
12 Correct 41 ms 70748 KB Output is correct
13 Correct 46 ms 70672 KB Output is correct
14 Correct 44 ms 70980 KB Output is correct
15 Correct 47 ms 71036 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70660 KB Output is correct
2 Correct 41 ms 70768 KB Output is correct
3 Correct 40 ms 70684 KB Output is correct
4 Correct 39 ms 70724 KB Output is correct
5 Correct 39 ms 70684 KB Output is correct
6 Correct 41 ms 70852 KB Output is correct
7 Correct 40 ms 70668 KB Output is correct
8 Correct 43 ms 70700 KB Output is correct
9 Correct 43 ms 70680 KB Output is correct
10 Correct 40 ms 70840 KB Output is correct
11 Correct 43 ms 71016 KB Output is correct
12 Correct 42 ms 70856 KB Output is correct
13 Correct 40 ms 70796 KB Output is correct
14 Correct 44 ms 71008 KB Output is correct
15 Correct 41 ms 71048 KB Output is correct
16 Correct 42 ms 70852 KB Output is correct
17 Correct 43 ms 71556 KB Output is correct
18 Correct 42 ms 71012 KB Output is correct
19 Correct 41 ms 70920 KB Output is correct
20 Correct 41 ms 70948 KB Output is correct
21 Correct 46 ms 70860 KB Output is correct
22 Correct 41 ms 71036 KB Output is correct
23 Correct 40 ms 71048 KB Output is correct
24 Correct 47 ms 71448 KB Output is correct
25 Correct 40 ms 71116 KB Output is correct
26 Correct 45 ms 71176 KB Output is correct
27 Correct 51 ms 71036 KB Output is correct
28 Correct 45 ms 71888 KB Output is correct
29 Correct 54 ms 73924 KB Output is correct
30 Correct 44 ms 71800 KB Output is correct
31 Correct 47 ms 72388 KB Output is correct
32 Correct 45 ms 71996 KB Output is correct
33 Correct 66 ms 76996 KB Output is correct
34 Correct 70 ms 77028 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70728 KB Output is correct
2 Correct 39 ms 70724 KB Output is correct
3 Correct 40 ms 70644 KB Output is correct
4 Correct 39 ms 70796 KB Output is correct
5 Correct 40 ms 70756 KB Output is correct
6 Correct 45 ms 70724 KB Output is correct
7 Correct 40 ms 70764 KB Output is correct
8 Correct 42 ms 70684 KB Output is correct
9 Correct 40 ms 70720 KB Output is correct
10 Correct 39 ms 70712 KB Output is correct
11 Correct 40 ms 70988 KB Output is correct
12 Correct 41 ms 70688 KB Output is correct
13 Correct 41 ms 70696 KB Output is correct
14 Correct 41 ms 71024 KB Output is correct
15 Correct 42 ms 71092 KB Output is correct
16 Correct 47 ms 70936 KB Output is correct
17 Correct 44 ms 71456 KB Output is correct
18 Correct 44 ms 71028 KB Output is correct
19 Correct 40 ms 71028 KB Output is correct
20 Correct 42 ms 70888 KB Output is correct
21 Correct 40 ms 70860 KB Output is correct
22 Correct 41 ms 71064 KB Output is correct
23 Correct 45 ms 71048 KB Output is correct
24 Correct 44 ms 71372 KB Output is correct
25 Correct 42 ms 71168 KB Output is correct
26 Correct 44 ms 71164 KB Output is correct
27 Correct 44 ms 71096 KB Output is correct
28 Correct 45 ms 71928 KB Output is correct
29 Correct 65 ms 73924 KB Output is correct
30 Correct 43 ms 71656 KB Output is correct
31 Correct 48 ms 72428 KB Output is correct
32 Correct 44 ms 71884 KB Output is correct
33 Correct 66 ms 76984 KB Output is correct
34 Correct 66 ms 77016 KB Output is correct
35 Correct 76 ms 76384 KB Output is correct
36 Correct 45 ms 71620 KB Output is correct
37 Correct 105 ms 80276 KB Output is correct
38 Correct 98 ms 79616 KB Output is correct
39 Correct 95 ms 79812 KB Output is correct
40 Correct 103 ms 79688 KB Output is correct
41 Correct 104 ms 79624 KB Output is correct
42 Correct 51 ms 71364 KB Output is correct
43 Correct 51 ms 71428 KB Output is correct
44 Correct 51 ms 71116 KB Output is correct
45 Correct 223 ms 96180 KB Output is correct
46 Correct 237 ms 96256 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70720 KB Output is correct
2 Correct 41 ms 70684 KB Output is correct
3 Correct 40 ms 70688 KB Output is correct
4 Correct 40 ms 70756 KB Output is correct
5 Correct 41 ms 70672 KB Output is correct
6 Correct 41 ms 70692 KB Output is correct
7 Correct 42 ms 70752 KB Output is correct
8 Correct 41 ms 70732 KB Output is correct
9 Correct 41 ms 70764 KB Output is correct
10 Correct 40 ms 70748 KB Output is correct
11 Correct 42 ms 70980 KB Output is correct
12 Correct 42 ms 70916 KB Output is correct
13 Correct 41 ms 70704 KB Output is correct
14 Correct 41 ms 71000 KB Output is correct
15 Correct 42 ms 71024 KB Output is correct
16 Correct 41 ms 70860 KB Output is correct
17 Correct 45 ms 71492 KB Output is correct
18 Correct 46 ms 71108 KB Output is correct
19 Correct 42 ms 71000 KB Output is correct
20 Correct 43 ms 70980 KB Output is correct
21 Correct 41 ms 70884 KB Output is correct
22 Correct 42 ms 70948 KB Output is correct
23 Correct 41 ms 71028 KB Output is correct
24 Correct 45 ms 71328 KB Output is correct
25 Correct 44 ms 71168 KB Output is correct
26 Correct 47 ms 71172 KB Output is correct
27 Correct 42 ms 71108 KB Output is correct
28 Correct 45 ms 71884 KB Output is correct
29 Correct 58 ms 73908 KB Output is correct
30 Correct 44 ms 71668 KB Output is correct
31 Correct 48 ms 72388 KB Output is correct
32 Correct 44 ms 71944 KB Output is correct
33 Correct 67 ms 77136 KB Output is correct
34 Correct 70 ms 77008 KB Output is correct
35 Correct 79 ms 76464 KB Output is correct
36 Correct 47 ms 71736 KB Output is correct
37 Correct 108 ms 80320 KB Output is correct
38 Correct 108 ms 79756 KB Output is correct
39 Correct 95 ms 79700 KB Output is correct
40 Correct 105 ms 79696 KB Output is correct
41 Correct 110 ms 79660 KB Output is correct
42 Correct 51 ms 71364 KB Output is correct
43 Correct 53 ms 71288 KB Output is correct
44 Correct 51 ms 71076 KB Output is correct
45 Correct 227 ms 96180 KB Output is correct
46 Correct 234 ms 96196 KB Output is correct
47 Correct 345 ms 110020 KB Output is correct
48 Correct 81 ms 82732 KB Output is correct
49 Correct 68 ms 78260 KB Output is correct
50 Correct 69 ms 78216 KB Output is correct
51 Correct 142 ms 87580 KB Output is correct
52 Correct 147 ms 88996 KB Output is correct
53 Correct 70 ms 75872 KB Output is correct
54 Correct 44 ms 72444 KB Output is correct
55 Correct 46 ms 73696 KB Output is correct
56 Correct 64 ms 73528 KB Output is correct
57 Correct 159 ms 93428 KB Output is correct
58 Correct 64 ms 74616 KB Output is correct
59 Correct 66 ms 76068 KB Output is correct
60 Correct 78 ms 77548 KB Output is correct
61 Correct 91 ms 76676 KB Output is correct
62 Correct 158 ms 96792 KB Output is correct
63 Correct 957 ms 189324 KB Output is correct
64 Execution timed out 1097 ms 216424 KB Time limit exceeded
65 Halted 0 ms 0 KB -