oj.uz

Submission #459408

# Submission time Handle Problem Language Result Execution time Memory
459408 2021-08-08T13:07:35 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 936 ms 262148 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=5000000;
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 66 ms 117624 KB Output is correct
2 Correct 69 ms 117684 KB Output is correct
3 Correct 69 ms 117708 KB Output is correct
4 Correct 66 ms 117644 KB Output is correct
5 Correct 76 ms 117700 KB Output is correct
6 Correct 66 ms 117612 KB Output is correct
7 Correct 68 ms 117656 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 117648 KB Output is correct
2 Correct 64 ms 117712 KB Output is correct
3 Correct 66 ms 117736 KB Output is correct
4 Correct 66 ms 117696 KB Output is correct
5 Correct 76 ms 117604 KB Output is correct
6 Correct 69 ms 117740 KB Output is correct
7 Correct 70 ms 117728 KB Output is correct
8 Correct 67 ms 117700 KB Output is correct
9 Correct 71 ms 117728 KB Output is correct
10 Correct 68 ms 117844 KB Output is correct
11 Correct 71 ms 117952 KB Output is correct
12 Correct 73 ms 117688 KB Output is correct
13 Correct 69 ms 117756 KB Output is correct
14 Correct 68 ms 117956 KB Output is correct
15 Correct 69 ms 118084 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 117716 KB Output is correct
2 Correct 65 ms 117668 KB Output is correct
3 Correct 78 ms 117620 KB Output is correct
4 Correct 68 ms 117604 KB Output is correct
5 Correct 66 ms 117724 KB Output is correct
6 Correct 67 ms 117660 KB Output is correct
7 Correct 68 ms 117700 KB Output is correct
8 Correct 66 ms 117628 KB Output is correct
9 Correct 67 ms 117616 KB Output is correct
10 Correct 66 ms 117776 KB Output is correct
11 Correct 69 ms 117992 KB Output is correct
12 Correct 75 ms 117700 KB Output is correct
13 Correct 68 ms 117684 KB Output is correct
14 Correct 68 ms 118088 KB Output is correct
15 Correct 68 ms 117988 KB Output is correct
16 Correct 67 ms 117828 KB Output is correct
17 Correct 72 ms 118596 KB Output is correct
18 Correct 68 ms 118084 KB Output is correct
19 Correct 68 ms 117956 KB Output is correct
20 Correct 66 ms 117808 KB Output is correct
21 Correct 69 ms 117872 KB Output is correct
22 Correct 68 ms 117952 KB Output is correct
23 Correct 76 ms 118040 KB Output is correct
24 Correct 71 ms 118340 KB Output is correct
25 Correct 71 ms 118084 KB Output is correct
26 Correct 71 ms 118168 KB Output is correct
27 Correct 69 ms 118060 KB Output is correct
28 Correct 72 ms 118932 KB Output is correct
29 Correct 81 ms 120872 KB Output is correct
30 Correct 82 ms 118580 KB Output is correct
31 Correct 73 ms 119444 KB Output is correct
32 Correct 73 ms 118864 KB Output is correct
33 Correct 94 ms 123900 KB Output is correct
34 Correct 96 ms 123996 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 117676 KB Output is correct
2 Correct 67 ms 117720 KB Output is correct
3 Correct 68 ms 117640 KB Output is correct
4 Correct 70 ms 117620 KB Output is correct
5 Correct 67 ms 117772 KB Output is correct
6 Correct 75 ms 117636 KB Output is correct
7 Correct 75 ms 117728 KB Output is correct
8 Correct 64 ms 117736 KB Output is correct
9 Correct 68 ms 117712 KB Output is correct
10 Correct 69 ms 117696 KB Output is correct
11 Correct 69 ms 117988 KB Output is correct
12 Correct 67 ms 117660 KB Output is correct
13 Correct 68 ms 117700 KB Output is correct
14 Correct 70 ms 118056 KB Output is correct
15 Correct 68 ms 118040 KB Output is correct
16 Correct 66 ms 117872 KB Output is correct
17 Correct 73 ms 118420 KB Output is correct
18 Correct 68 ms 118096 KB Output is correct
19 Correct 69 ms 117944 KB Output is correct
20 Correct 75 ms 117916 KB Output is correct
21 Correct 68 ms 117784 KB Output is correct
22 Correct 69 ms 117976 KB Output is correct
23 Correct 70 ms 117996 KB Output is correct
24 Correct 73 ms 118296 KB Output is correct
25 Correct 85 ms 118132 KB Output is correct
26 Correct 67 ms 118032 KB Output is correct
27 Correct 70 ms 118076 KB Output is correct
28 Correct 73 ms 118880 KB Output is correct
29 Correct 79 ms 120992 KB Output is correct
30 Correct 75 ms 118640 KB Output is correct
31 Correct 74 ms 119356 KB Output is correct
32 Correct 70 ms 119016 KB Output is correct
33 Correct 92 ms 123956 KB Output is correct
34 Correct 96 ms 123924 KB Output is correct
35 Correct 100 ms 123460 KB Output is correct
36 Correct 72 ms 118660 KB Output is correct
37 Correct 122 ms 127196 KB Output is correct
38 Correct 131 ms 126660 KB Output is correct
39 Correct 131 ms 126604 KB Output is correct
40 Correct 130 ms 126676 KB Output is correct
41 Correct 124 ms 126624 KB Output is correct
42 Correct 78 ms 118368 KB Output is correct
43 Correct 78 ms 118260 KB Output is correct
44 Correct 82 ms 118084 KB Output is correct
45 Correct 248 ms 143148 KB Output is correct
46 Correct 245 ms 143188 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 117692 KB Output is correct
2 Correct 66 ms 117780 KB Output is correct
3 Correct 70 ms 117728 KB Output is correct
4 Correct 78 ms 117708 KB Output is correct
5 Correct 68 ms 117604 KB Output is correct
6 Correct 68 ms 117612 KB Output is correct
7 Correct 67 ms 117656 KB Output is correct
8 Correct 68 ms 117700 KB Output is correct
9 Correct 67 ms 117632 KB Output is correct
10 Correct 70 ms 117768 KB Output is correct
11 Correct 68 ms 117984 KB Output is correct
12 Correct 70 ms 117760 KB Output is correct
13 Correct 66 ms 117652 KB Output is correct
14 Correct 70 ms 117956 KB Output is correct
15 Correct 70 ms 118068 KB Output is correct
16 Correct 65 ms 117824 KB Output is correct
17 Correct 77 ms 118484 KB Output is correct
18 Correct 67 ms 118084 KB Output is correct
19 Correct 67 ms 117960 KB Output is correct
20 Correct 73 ms 117816 KB Output is correct
21 Correct 67 ms 117828 KB Output is correct
22 Correct 68 ms 117932 KB Output is correct
23 Correct 69 ms 118016 KB Output is correct
24 Correct 69 ms 118404 KB Output is correct
25 Correct 76 ms 118064 KB Output is correct
26 Correct 80 ms 118108 KB Output is correct
27 Correct 69 ms 117996 KB Output is correct
28 Correct 71 ms 118952 KB Output is correct
29 Correct 82 ms 120808 KB Output is correct
30 Correct 72 ms 118596 KB Output is correct
31 Correct 75 ms 119584 KB Output is correct
32 Correct 71 ms 118872 KB Output is correct
33 Correct 93 ms 123884 KB Output is correct
34 Correct 95 ms 123956 KB Output is correct
35 Correct 105 ms 123460 KB Output is correct
36 Correct 75 ms 118640 KB Output is correct
37 Correct 132 ms 127352 KB Output is correct
38 Correct 120 ms 126692 KB Output is correct
39 Correct 125 ms 126696 KB Output is correct
40 Correct 123 ms 126692 KB Output is correct
41 Correct 122 ms 126664 KB Output is correct
42 Correct 78 ms 118348 KB Output is correct
43 Correct 80 ms 118224 KB Output is correct
44 Correct 81 ms 118044 KB Output is correct
45 Correct 246 ms 143300 KB Output is correct
46 Correct 246 ms 143152 KB Output is correct
47 Correct 324 ms 156880 KB Output is correct
48 Correct 108 ms 129884 KB Output is correct
49 Correct 96 ms 125236 KB Output is correct
50 Correct 111 ms 125276 KB Output is correct
51 Correct 170 ms 134724 KB Output is correct
52 Correct 175 ms 136060 KB Output is correct
53 Correct 104 ms 122816 KB Output is correct
54 Correct 71 ms 119316 KB Output is correct
55 Correct 77 ms 120584 KB Output is correct
56 Correct 91 ms 120596 KB Output is correct
57 Correct 192 ms 140372 KB Output is correct
58 Correct 87 ms 121540 KB Output is correct
59 Correct 96 ms 123124 KB Output is correct
60 Correct 100 ms 124484 KB Output is correct
61 Correct 96 ms 123712 KB Output is correct
62 Correct 172 ms 143828 KB Output is correct
63 Correct 936 ms 236572 KB Output is correct
64 Runtime error 418 ms 262148 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -