oj.uz

Submission #459397

# Submission time Handle Problem Language Result Execution time Memory
459397 2021-08-08T13:00:25 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 329 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=10000000;
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 131 ms 235140 KB Output is correct
2 Correct 128 ms 235100 KB Output is correct
3 Correct 146 ms 235080 KB Output is correct
4 Correct 128 ms 235104 KB Output is correct
5 Correct 134 ms 235096 KB Output is correct
6 Correct 130 ms 235088 KB Output is correct
7 Correct 128 ms 235084 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 235028 KB Output is correct
2 Correct 131 ms 235104 KB Output is correct
3 Correct 134 ms 235104 KB Output is correct
4 Correct 133 ms 235020 KB Output is correct
5 Correct 133 ms 235140 KB Output is correct
6 Correct 131 ms 235076 KB Output is correct
7 Correct 127 ms 235140 KB Output is correct
8 Correct 130 ms 235096 KB Output is correct
9 Correct 134 ms 235148 KB Output is correct
10 Correct 128 ms 235184 KB Output is correct
11 Correct 128 ms 235400 KB Output is correct
12 Correct 133 ms 235096 KB Output is correct
13 Correct 127 ms 235076 KB Output is correct
14 Correct 131 ms 235556 KB Output is correct
15 Correct 131 ms 235392 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 235112 KB Output is correct
2 Correct 134 ms 235140 KB Output is correct
3 Correct 131 ms 235136 KB Output is correct
4 Correct 131 ms 235060 KB Output is correct
5 Correct 128 ms 235080 KB Output is correct
6 Correct 128 ms 235040 KB Output is correct
7 Correct 127 ms 235016 KB Output is correct
8 Correct 129 ms 235076 KB Output is correct
9 Correct 127 ms 235084 KB Output is correct
10 Correct 127 ms 235224 KB Output is correct
11 Correct 129 ms 235384 KB Output is correct
12 Correct 129 ms 235296 KB Output is correct
13 Correct 130 ms 235140 KB Output is correct
14 Correct 133 ms 235472 KB Output is correct
15 Correct 129 ms 235608 KB Output is correct
16 Correct 128 ms 235312 KB Output is correct
17 Correct 134 ms 235848 KB Output is correct
18 Correct 134 ms 235500 KB Output is correct
19 Correct 131 ms 235404 KB Output is correct
20 Correct 127 ms 235268 KB Output is correct
21 Correct 128 ms 235352 KB Output is correct
22 Correct 128 ms 235332 KB Output is correct
23 Correct 127 ms 235444 KB Output is correct
24 Correct 136 ms 235844 KB Output is correct
25 Correct 131 ms 235556 KB Output is correct
26 Correct 129 ms 235540 KB Output is correct
27 Correct 138 ms 235412 KB Output is correct
28 Correct 136 ms 236452 KB Output is correct
29 Correct 143 ms 238308 KB Output is correct
30 Correct 129 ms 236060 KB Output is correct
31 Correct 133 ms 236880 KB Output is correct
32 Correct 138 ms 236352 KB Output is correct
33 Correct 156 ms 241348 KB Output is correct
34 Correct 156 ms 241364 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 235120 KB Output is correct
2 Correct 133 ms 235060 KB Output is correct
3 Correct 128 ms 235136 KB Output is correct
4 Correct 127 ms 235072 KB Output is correct
5 Correct 133 ms 235136 KB Output is correct
6 Correct 129 ms 235116 KB Output is correct
7 Correct 135 ms 235076 KB Output is correct
8 Correct 136 ms 235148 KB Output is correct
9 Correct 131 ms 235080 KB Output is correct
10 Correct 130 ms 235252 KB Output is correct
11 Correct 133 ms 235392 KB Output is correct
12 Correct 146 ms 235112 KB Output is correct
13 Correct 131 ms 235204 KB Output is correct
14 Correct 162 ms 235404 KB Output is correct
15 Correct 131 ms 235444 KB Output is correct
16 Correct 127 ms 235372 KB Output is correct
17 Correct 132 ms 235824 KB Output is correct
18 Correct 130 ms 235492 KB Output is correct
19 Correct 142 ms 235496 KB Output is correct
20 Correct 130 ms 235332 KB Output is correct
21 Correct 129 ms 235244 KB Output is correct
22 Correct 130 ms 235416 KB Output is correct
23 Correct 134 ms 235444 KB Output is correct
24 Correct 131 ms 235792 KB Output is correct
25 Correct 133 ms 235444 KB Output is correct
26 Correct 140 ms 235780 KB Output is correct
27 Correct 133 ms 235444 KB Output is correct
28 Correct 137 ms 236356 KB Output is correct
29 Correct 143 ms 238336 KB Output is correct
30 Correct 134 ms 236044 KB Output is correct
31 Correct 135 ms 236868 KB Output is correct
32 Correct 134 ms 236376 KB Output is correct
33 Correct 182 ms 241372 KB Output is correct
34 Correct 160 ms 241376 KB Output is correct
35 Correct 169 ms 240816 KB Output is correct
36 Correct 139 ms 236024 KB Output is correct
37 Correct 191 ms 244676 KB Output is correct
38 Correct 183 ms 244084 KB Output is correct
39 Correct 185 ms 244016 KB Output is correct
40 Correct 186 ms 244104 KB Output is correct
41 Correct 202 ms 244052 KB Output is correct
42 Correct 156 ms 235676 KB Output is correct
43 Correct 145 ms 235716 KB Output is correct
44 Correct 142 ms 235552 KB Output is correct
45 Correct 329 ms 260604 KB Output is correct
46 Correct 313 ms 260576 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 235060 KB Output is correct
2 Correct 132 ms 235140 KB Output is correct
3 Correct 130 ms 235100 KB Output is correct
4 Correct 131 ms 235104 KB Output is correct
5 Correct 129 ms 235140 KB Output is correct
6 Correct 126 ms 235072 KB Output is correct
7 Correct 131 ms 235188 KB Output is correct
8 Correct 129 ms 235140 KB Output is correct
9 Correct 130 ms 235060 KB Output is correct
10 Correct 150 ms 235224 KB Output is correct
11 Correct 154 ms 235332 KB Output is correct
12 Correct 131 ms 235140 KB Output is correct
13 Correct 146 ms 235148 KB Output is correct
14 Correct 151 ms 235460 KB Output is correct
15 Correct 136 ms 235548 KB Output is correct
16 Correct 132 ms 235288 KB Output is correct
17 Correct 131 ms 235908 KB Output is correct
18 Correct 128 ms 235456 KB Output is correct
19 Correct 133 ms 235320 KB Output is correct
20 Correct 131 ms 235320 KB Output is correct
21 Correct 131 ms 235204 KB Output is correct
22 Correct 128 ms 235332 KB Output is correct
23 Correct 131 ms 235424 KB Output is correct
24 Correct 133 ms 235728 KB Output is correct
25 Correct 131 ms 235468 KB Output is correct
26 Correct 132 ms 235648 KB Output is correct
27 Correct 132 ms 235516 KB Output is correct
28 Correct 135 ms 236464 KB Output is correct
29 Correct 152 ms 238340 KB Output is correct
30 Correct 130 ms 235984 KB Output is correct
31 Correct 134 ms 236812 KB Output is correct
32 Correct 140 ms 236332 KB Output is correct
33 Correct 157 ms 241348 KB Output is correct
34 Correct 161 ms 241384 KB Output is correct
35 Correct 171 ms 240776 KB Output is correct
36 Correct 144 ms 236128 KB Output is correct
37 Correct 190 ms 244660 KB Output is correct
38 Correct 188 ms 244080 KB Output is correct
39 Correct 185 ms 244016 KB Output is correct
40 Correct 192 ms 244084 KB Output is correct
41 Correct 184 ms 244108 KB Output is correct
42 Correct 142 ms 235816 KB Output is correct
43 Correct 138 ms 235656 KB Output is correct
44 Correct 142 ms 235516 KB Output is correct
45 Correct 310 ms 260640 KB Output is correct
46 Correct 311 ms 260644 KB Output is correct
47 Runtime error 183 ms 262148 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -