oj.uz

Submission #1019170

# Submission time Handle Problem Language Result Execution time Memory
1019170 2024-07-10T14:28:31 Z amine_aroua Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 366 ms 440 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n , m;
    cin>>n>>m;
    int sz = (int)sqrt(n);
    vector<vector<int>> p(n);
    vector<vector<int>> dist(n , vector<int>(sz +1 , INT32_MAX));
    vector<vector<bool>> vis(n , vector<bool>(sz + 1 , 0));
    queue<tuple<int ,int , int>> q;
    int trg = 0;
    for(int i = 0 ; i < m; i++)
    {
        int a , b;
        cin>>a>>b;
        if(i == 0)
        {
            dist[a][0] = 0;
            q.push({0 , a , 0});
        }
        if(i == 1)
        {
            trg = a;
        }
        p[a].push_back(b);
    }
    while(!q.empty())
    {
        auto [d , tp , last] = q.front();
        q.pop();
        if(vis[tp][last])
            continue;
        vis[tp][last] = 1;
        vector<int> all = p[tp];
        all.push_back(last);
        for(auto P : all)
        {
            if(P == 0)
                continue;
            if(P > sz)
            {
                for(int k = 1 ; tp + k * P < n || tp + k * P >= 0; k++)
                {
                    if(k * P + tp < n && dist[k * P + tp][0] > dist[tp][last] + k)
                    {
                        dist[k * P + tp][0] = dist[tp][last] + k;
                        q.push({dist[k * P + tp][0] , k * P + tp , 0});
                    }
                    if(tp - k * P >= 0 && dist[tp - k * P][0] > dist[tp][last] + k)
                    {
                        dist[tp - k * P][0] = dist[tp][last] + k;
                        q.push({dist[tp - k * P][0] , tp - k * P , 0});
                    }
                }
            }
            else
            {
                if(P + tp < n)
                {
                    if(dist[P + tp][P] > dist[tp][last] + 1)
                    {
                        dist[P + tp][P] = dist[tp][last] + 1;
                        q.push({dist[P + tp][P] , P + tp , P});
                    }
                }
                if(tp - P >= 0)
                {
                    if(dist[tp - P][P] > dist[tp][last] + 1)
                    {
                        dist[tp - P][P] = dist[tp][last] + 1;
                        q.push({dist[tp - P][P] , tp - P , P});
                    }
                }
            }
        }
    }
    int mn = INT32_MAX;
    for(int i = 0 ; i <= sz ; i++)
    {
        mn = min(mn , dist[trg][i]);
    }
    cout<<(mn == INT32_MAX ? -1 : mn);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 357 ms 428 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 366 ms 440 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 353 ms 428 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 362 ms 428 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 358 ms 440 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -