oj.uz

Submission #459365

# Submission time Handle Problem Language Result Execution time Memory
459365 2021-08-08T12:34:20 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 114 ms 188312 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].sec;
    }
    sort(BP.begin(), BP.end(), cmp1);
    BP.erase(unique(BP.begin(), BP.end()), BP.end());
    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(j==BP[cur].fir)
            {
                adj[j].push_back({idx, 0});
                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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 188312 KB Output is correct
2 Correct 114 ms 188096 KB Output is correct
3 Incorrect 101 ms 188092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 188276 KB Output is correct
2 Correct 101 ms 188120 KB Output is correct
3 Incorrect 103 ms 188100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 188056 KB Output is correct
2 Correct 109 ms 188172 KB Output is correct
3 Incorrect 105 ms 188124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188176 KB Output is correct
2 Correct 100 ms 188100 KB Output is correct
3 Incorrect 100 ms 188176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 188148 KB Output is correct
2 Correct 110 ms 188272 KB Output is correct
3 Incorrect 103 ms 188056 KB Output isn't correct
4 Halted 0 ms 0 KB -