oj.uz

Submission #459393

# Submission time Handle Problem Language Result Execution time Memory
459393 2021-08-08T12:54:44 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 113 ms 188336 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 102 ms 188104 KB Output is correct
2 Correct 102 ms 188080 KB Output is correct
3 Correct 102 ms 188068 KB Output is correct
4 Correct 104 ms 188128 KB Output is correct
5 Correct 102 ms 188080 KB Output is correct
6 Correct 105 ms 188156 KB Output is correct
7 Correct 104 ms 188100 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 188092 KB Output is correct
2 Correct 106 ms 188064 KB Output is correct
3 Correct 104 ms 188128 KB Output is correct
4 Correct 105 ms 188144 KB Output is correct
5 Correct 112 ms 188120 KB Output is correct
6 Correct 106 ms 188100 KB Output is correct
7 Correct 105 ms 188056 KB Output is correct
8 Correct 112 ms 188068 KB Output is correct
9 Correct 106 ms 188100 KB Output is correct
10 Incorrect 107 ms 188244 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188076 KB Output is correct
2 Correct 105 ms 188216 KB Output is correct
3 Correct 113 ms 188168 KB Output is correct
4 Correct 106 ms 188136 KB Output is correct
5 Correct 103 ms 188140 KB Output is correct
6 Correct 104 ms 188088 KB Output is correct
7 Correct 104 ms 188176 KB Output is correct
8 Correct 105 ms 188100 KB Output is correct
9 Correct 102 ms 188108 KB Output is correct
10 Incorrect 107 ms 188232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188136 KB Output is correct
2 Correct 105 ms 188192 KB Output is correct
3 Correct 103 ms 188128 KB Output is correct
4 Correct 108 ms 188100 KB Output is correct
5 Correct 100 ms 188096 KB Output is correct
6 Correct 107 ms 188072 KB Output is correct
7 Correct 105 ms 188100 KB Output is correct
8 Correct 104 ms 188108 KB Output is correct
9 Correct 104 ms 188188 KB Output is correct
10 Incorrect 106 ms 188228 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 188100 KB Output is correct
2 Correct 102 ms 188112 KB Output is correct
3 Correct 106 ms 188160 KB Output is correct
4 Correct 105 ms 188160 KB Output is correct
5 Correct 103 ms 188136 KB Output is correct
6 Correct 104 ms 188172 KB Output is correct
7 Correct 104 ms 188148 KB Output is correct
8 Correct 106 ms 188100 KB Output is correct
9 Correct 103 ms 188100 KB Output is correct
10 Incorrect 105 ms 188336 KB Output isn't correct
11 Halted 0 ms 0 KB -