oj.uz

Submission #459395

# Submission time Handle Problem Language Result Execution time Memory
459395 2021-08-08T12:59:01 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 394 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=8000000;
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(pii 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++;
        }
    }
    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 109 ms 188132 KB Output is correct
2 Correct 105 ms 188184 KB Output is correct
3 Correct 105 ms 188180 KB Output is correct
4 Correct 107 ms 188100 KB Output is correct
5 Correct 106 ms 188068 KB Output is correct
6 Correct 103 ms 188184 KB Output is correct
7 Correct 106 ms 188100 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 188140 KB Output is correct
2 Correct 103 ms 188084 KB Output is correct
3 Correct 108 ms 188172 KB Output is correct
4 Correct 107 ms 188064 KB Output is correct
5 Correct 104 ms 188148 KB Output is correct
6 Correct 109 ms 188080 KB Output is correct
7 Correct 103 ms 188080 KB Output is correct
8 Correct 110 ms 188184 KB Output is correct
9 Correct 110 ms 188152 KB Output is correct
10 Correct 103 ms 188268 KB Output is correct
11 Correct 106 ms 188348 KB Output is correct
12 Correct 106 ms 188188 KB Output is correct
13 Correct 104 ms 188124 KB Output is correct
14 Correct 106 ms 188524 KB Output is correct
15 Correct 113 ms 188492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188136 KB Output is correct
2 Correct 103 ms 188100 KB Output is correct
3 Correct 104 ms 188100 KB Output is correct
4 Correct 105 ms 188152 KB Output is correct
5 Correct 105 ms 188092 KB Output is correct
6 Correct 110 ms 188216 KB Output is correct
7 Correct 103 ms 188148 KB Output is correct
8 Correct 113 ms 188172 KB Output is correct
9 Correct 105 ms 188100 KB Output is correct
10 Correct 101 ms 188144 KB Output is correct
11 Correct 120 ms 188348 KB Output is correct
12 Correct 102 ms 188228 KB Output is correct
13 Correct 103 ms 188200 KB Output is correct
14 Correct 108 ms 188536 KB Output is correct
15 Correct 111 ms 188456 KB Output is correct
16 Correct 105 ms 188356 KB Output is correct
17 Correct 110 ms 188960 KB Output is correct
18 Correct 104 ms 188444 KB Output is correct
19 Correct 103 ms 188416 KB Output is correct
20 Correct 104 ms 188280 KB Output is correct
21 Correct 106 ms 188344 KB Output is correct
22 Correct 105 ms 188408 KB Output is correct
23 Correct 111 ms 188484 KB Output is correct
24 Correct 107 ms 188816 KB Output is correct
25 Correct 104 ms 188532 KB Output is correct
26 Correct 105 ms 188576 KB Output is correct
27 Correct 107 ms 188480 KB Output is correct
28 Correct 108 ms 189412 KB Output is correct
29 Correct 118 ms 191476 KB Output is correct
30 Correct 108 ms 189124 KB Output is correct
31 Correct 109 ms 189904 KB Output is correct
32 Correct 111 ms 189420 KB Output is correct
33 Correct 131 ms 194456 KB Output is correct
34 Correct 131 ms 194392 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 188152 KB Output is correct
2 Correct 104 ms 188252 KB Output is correct
3 Correct 103 ms 188144 KB Output is correct
4 Correct 102 ms 188096 KB Output is correct
5 Correct 105 ms 188100 KB Output is correct
6 Correct 107 ms 188156 KB Output is correct
7 Correct 107 ms 188068 KB Output is correct
8 Correct 105 ms 188232 KB Output is correct
9 Correct 107 ms 188128 KB Output is correct
10 Correct 104 ms 188228 KB Output is correct
11 Correct 104 ms 188396 KB Output is correct
12 Correct 111 ms 188140 KB Output is correct
13 Correct 112 ms 188184 KB Output is correct
14 Correct 108 ms 188540 KB Output is correct
15 Correct 118 ms 188440 KB Output is correct
16 Correct 107 ms 188360 KB Output is correct
17 Correct 109 ms 188964 KB Output is correct
18 Correct 107 ms 188468 KB Output is correct
19 Correct 102 ms 188356 KB Output is correct
20 Correct 106 ms 188336 KB Output is correct
21 Correct 103 ms 188428 KB Output is correct
22 Correct 106 ms 188428 KB Output is correct
23 Correct 117 ms 188480 KB Output is correct
24 Correct 107 ms 188812 KB Output is correct
25 Correct 117 ms 188612 KB Output is correct
26 Correct 105 ms 188612 KB Output is correct
27 Correct 109 ms 188572 KB Output is correct
28 Correct 107 ms 189424 KB Output is correct
29 Correct 117 ms 191260 KB Output is correct
30 Correct 108 ms 189072 KB Output is correct
31 Correct 116 ms 189800 KB Output is correct
32 Correct 107 ms 189340 KB Output is correct
33 Correct 131 ms 194460 KB Output is correct
34 Correct 133 ms 194504 KB Output is correct
35 Correct 136 ms 194052 KB Output is correct
36 Correct 118 ms 189104 KB Output is correct
37 Correct 158 ms 197864 KB Output is correct
38 Correct 170 ms 197320 KB Output is correct
39 Correct 157 ms 197432 KB Output is correct
40 Correct 166 ms 197316 KB Output is correct
41 Correct 155 ms 197312 KB Output is correct
42 Correct 117 ms 189036 KB Output is correct
43 Correct 115 ms 188928 KB Output is correct
44 Correct 123 ms 188684 KB Output is correct
45 Correct 285 ms 213908 KB Output is correct
46 Correct 298 ms 213780 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 188092 KB Output is correct
2 Correct 107 ms 188172 KB Output is correct
3 Correct 109 ms 188236 KB Output is correct
4 Correct 105 ms 188172 KB Output is correct
5 Correct 108 ms 188100 KB Output is correct
6 Correct 102 ms 188144 KB Output is correct
7 Correct 102 ms 188172 KB Output is correct
8 Correct 109 ms 188088 KB Output is correct
9 Correct 105 ms 188112 KB Output is correct
10 Correct 120 ms 188204 KB Output is correct
11 Correct 104 ms 188448 KB Output is correct
12 Correct 103 ms 188180 KB Output is correct
13 Correct 112 ms 188136 KB Output is correct
14 Correct 118 ms 188484 KB Output is correct
15 Correct 104 ms 188540 KB Output is correct
16 Correct 105 ms 188304 KB Output is correct
17 Correct 106 ms 188992 KB Output is correct
18 Correct 107 ms 188496 KB Output is correct
19 Correct 109 ms 188468 KB Output is correct
20 Correct 105 ms 188340 KB Output is correct
21 Correct 107 ms 188256 KB Output is correct
22 Correct 107 ms 188388 KB Output is correct
23 Correct 107 ms 188484 KB Output is correct
24 Correct 108 ms 188888 KB Output is correct
25 Correct 105 ms 188500 KB Output is correct
26 Correct 105 ms 188488 KB Output is correct
27 Correct 105 ms 188640 KB Output is correct
28 Correct 110 ms 189396 KB Output is correct
29 Correct 119 ms 191380 KB Output is correct
30 Correct 106 ms 189068 KB Output is correct
31 Correct 113 ms 189900 KB Output is correct
32 Correct 112 ms 189320 KB Output is correct
33 Correct 138 ms 194560 KB Output is correct
34 Correct 132 ms 194416 KB Output is correct
35 Correct 146 ms 194136 KB Output is correct
36 Correct 109 ms 189164 KB Output is correct
37 Correct 157 ms 197980 KB Output is correct
38 Correct 159 ms 197388 KB Output is correct
39 Correct 160 ms 197360 KB Output is correct
40 Correct 180 ms 197380 KB Output is correct
41 Correct 166 ms 197460 KB Output is correct
42 Correct 117 ms 189000 KB Output is correct
43 Correct 115 ms 188944 KB Output is correct
44 Correct 118 ms 188752 KB Output is correct
45 Correct 282 ms 213952 KB Output is correct
46 Correct 301 ms 213848 KB Output is correct
47 Correct 394 ms 227600 KB Output is correct
48 Correct 145 ms 200484 KB Output is correct
49 Correct 132 ms 195908 KB Output is correct
50 Correct 131 ms 195804 KB Output is correct
51 Correct 207 ms 205396 KB Output is correct
52 Correct 215 ms 206756 KB Output is correct
53 Correct 132 ms 193544 KB Output is correct
54 Correct 110 ms 189760 KB Output is correct
55 Correct 114 ms 191076 KB Output is correct
56 Correct 126 ms 191200 KB Output is correct
57 Correct 247 ms 210760 KB Output is correct
58 Correct 124 ms 192068 KB Output is correct
59 Correct 133 ms 193808 KB Output is correct
60 Correct 141 ms 195152 KB Output is correct
61 Correct 137 ms 194372 KB Output is correct
62 Correct 199 ms 214608 KB Output is correct
63 Runtime error 270 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -