oj.uz

답안 #459350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
459350 2021-08-08T12:19:29 Z azberjibiou Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 124 ms 190464 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 <int> v[mxN];
map <short, int> mp[mxN];
vector <pair<int, bool>> adj[mxM];
int idx;
int X, Y;
list <int> lst;
int dis[mxM];
bool Chk[mxM];
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;
    for(int i=1;i<=M;i++)
    {
        int b, p;
        cin >> b >> p;
        if(i==1)    X=b;
        if(i==2)    Y=b;
        if(mp[b].end()==mp[b].find(p))
        {
            for(int j=b%p;j<N;j+=p)
            {
                mp[j][p]=idx;
                if(j>=p)
                {
                    adj[idx].push_back({idx-1, 1});
                    adj[idx-1].push_back({idx, 1});
                }
                idx++;
            }
        }
        v[b].push_back(p);
    }
    for(int i=0;i<N;i++)
    {
        for(auto iter=mp[i].begin();iter!=mp[i].end();iter++)
        {
            adj[iter->sec].push_back({i, 0});
        }
        for(int nxt : v[i])
        {
            adj[i].push_back({mp[i][nxt], 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

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 190256 KB Output is correct
2 Correct 105 ms 190292 KB Output is correct
3 Correct 106 ms 190200 KB Output is correct
4 Correct 107 ms 190276 KB Output is correct
5 Correct 109 ms 190404 KB Output is correct
6 Correct 106 ms 190260 KB Output is correct
7 Correct 104 ms 190412 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 190232 KB Output is correct
2 Correct 107 ms 190192 KB Output is correct
3 Correct 104 ms 190212 KB Output is correct
4 Correct 103 ms 190288 KB Output is correct
5 Correct 103 ms 190256 KB Output is correct
6 Correct 106 ms 190300 KB Output is correct
7 Correct 110 ms 190240 KB Output is correct
8 Correct 105 ms 190276 KB Output is correct
9 Correct 106 ms 190280 KB Output is correct
10 Incorrect 105 ms 190424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 190284 KB Output is correct
2 Correct 103 ms 190200 KB Output is correct
3 Correct 107 ms 190296 KB Output is correct
4 Correct 105 ms 190404 KB Output is correct
5 Correct 104 ms 190272 KB Output is correct
6 Correct 104 ms 190204 KB Output is correct
7 Correct 106 ms 190296 KB Output is correct
8 Correct 104 ms 190248 KB Output is correct
9 Correct 103 ms 190200 KB Output is correct
10 Incorrect 106 ms 190404 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 190416 KB Output is correct
2 Correct 107 ms 190272 KB Output is correct
3 Correct 104 ms 190228 KB Output is correct
4 Correct 104 ms 190296 KB Output is correct
5 Correct 108 ms 190236 KB Output is correct
6 Correct 106 ms 190212 KB Output is correct
7 Correct 109 ms 190188 KB Output is correct
8 Correct 108 ms 190200 KB Output is correct
9 Correct 110 ms 190320 KB Output is correct
10 Incorrect 110 ms 190464 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 190204 KB Output is correct
2 Correct 104 ms 190204 KB Output is correct
3 Correct 107 ms 190332 KB Output is correct
4 Correct 113 ms 190264 KB Output is correct
5 Correct 124 ms 190276 KB Output is correct
6 Correct 106 ms 190192 KB Output is correct
7 Correct 106 ms 190276 KB Output is correct
8 Correct 105 ms 190180 KB Output is correct
9 Correct 109 ms 190316 KB Output is correct
10 Incorrect 111 ms 190460 KB Output isn't correct
11 Halted 0 ms 0 KB -