Submission #1173781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173781		pinruei	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1100 ms	122924 KiB

skyscraper

#pragma region //           https://oj.uz/problem/view/IOI08_printer
#include<bits/stdc++.h>
//#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define dqi deque<int>
#define dqpii deque<pii>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion

//#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;

constexpr int mxn=3e4+1, mxq=3e4+1;
constexpr bool debug = 0;
int n, m, srt, stp;
unordered_set<int> e[mxn];

void bfs()
{
    struct node
    {
        int u, v, dis;
        node(int u, int v, int d) : u(u), v(v), dis(d) {}
    };
    
    unordered_map<int, int> dis[mxn];
    deque<node> dq;
    bitset<mxn> vis;
    for(int i : e[srt])
    {
        dq.pb(node(srt, i, 0));
    }
    vis[srt] = 1;

    while(!dq.empty())
    {
        node cur = dq.front(); dq.pof;

        if(debug)
        {
            cout<<cur.u<<' '<<cur.v<<' '<<cur.dis<<'\n';
        }

        if(cur.dis>dis[cur.u][cur.v]) continue;
        if(cur.u == stp)
        {
            cout << cur.dis;
            return;
        }
        if(!vis[cur.u])
        {
            for(int i : e[cur.u])
            {
                if(dis[cur.u][i]==0 || cur.dis<dis[cur.u][i])
                {
                    dis[cur.u][i] = cur.dis;
                    dq.pf(node(cur.u, i, cur.dis));
                }
            }
            vis[cur.u] = 1;
        }
        f2(i, 2)
        {
            int nxt=i?+cur.v:-cur.v; nxt+=cur.u;
            if(nxt>=0 && nxt<n && (dis[nxt][cur.v]==0 || cur.dis+1<dis[nxt][cur.v]))
            {
                dis[nxt][cur.v] = cur.dis+1;
                dq.pb(node(nxt, cur.v, cur.dis+1));
            } 
        }
    }
    cout << -1;
}

signed main()//         https://oj.uz/problem/view/APIO16_boat
{   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    //input
    {
        cin >> n >> m;
        f2(i, m)
        {
            int u, v; cin>>u>>v;
            e[u].insert(v);
            i<2 && ((i?stp:srt) = u);
        }
    }

    bfs();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43