제출 #209584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209584		gratus907	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	20 ms	2556 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = false;
const int MX = 30202;

struct Edge
{
    int dest, w;
    bool operator<(const Edge &p) const
    {
        return w > p.w;
    }
};

bool relax(Edge edge, int u, int dist[])
{
    bool flag = 0;
    int v = edge.dest, w = edge.w;
    if (dist[v] > dist[u] + w && (dist[u]!=INF))
    {
        flag = true;
        dist[v] = dist[u]+w;
    }
    return flag;
}

void dijkstra(int dist[], int start, vector<Edge> graph[])
{
    fill(dist,dist+MX,INF);
    dist[start] = 0;
    priority_queue<Edge> pq;
    pq.push({start,0});
    while(!pq.empty())
    {
        Edge x = pq.top();
        int v = x.dest, w = x.w;
        pq.pop();
        if (w>dist[v])
            continue;
        for (auto ed : graph[v])
            if (relax(ed, v, dist))
                pq.push({ed.dest,dist[ed.dest]});
    }
}

int n, m;
vector <int> bi(30303, 0), pi(30303, 0);
vector <Edge> G[30303];
bitset <30303> mark[30303];
vector <int> doge[30303];
int distances[30303];
bool visit[30303];
void print_graph()
{
    for (int i = 0; i<n; i++)
    {
        for (auto it:G[i])
            printf("From %lld to %lld, %lld\n",i, it.dest, it.w);
    }
}
void print_dist()
{
    for (int i = 0; i<n; i++)
        printf("%lld ",distances[i]);
    printf("\n");
}
queue<pii> q;
int32_t main()
{
    cin >> n >> m;
    for (int i = 0; i<m; i++)
    {
        cin >> bi[i] >> pi[i];
        if (!mark[bi[i]][pi[i]] && i!=1)
        {
            mark[bi[i]][pi[i]] = true;
            doge[bi[i]].push_back(pi[i]);
        }
    }
    visit[bi[0]] = true;
    for (auto it:doge[bi[0]])
    {
        q.push({it, bi[0]});
    }
    while (!q.empty())
    {
        auto dg = q.front();
        q.pop();
        mark[dg.second][dg.first] = true;
        for (int i = 1; ; i++)
        {
            int u = dg.second+i*dg.first;
            if (u >= n) break;

            if (!visit[u])
            {
                visit[u] = true;
                for (auto unseen:doge[u])
                {
                    q.push({unseen, u});
                }
            }
            if (!mark[u][dg.first])
            {
                mark[u][dg.first] = true;
                G[dg.second].push_back({u, i});
            }
            else break;
        }
        for (int i = -1; ; i--)
        {
            int u = dg.second+i*dg.first;
            if (u < 0) break;

            if (!visit[u])
            {
                visit[u] = true;
                for (auto unseen:doge[u])
                {
                    q.push({unseen, u});
                }
            }
            if (!mark[u][dg.first])
            {
                mark[u][dg.first] = true;
                G[dg.second].push_back({u, -i});
            }
            else break;
        }
    }
    //print_graph();
    dijkstra(distances,bi[0],G);
    //print_dist();
    if (distances[bi[1]] >= INF)
    {
        printf("-1");
    }
    else
        printf("%lld\n",distances[bi[1]]);
}

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