Submission #1321769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321769		NValchanov	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	1014 ms	2148 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

typedef long long llong;

const int MAXN = 3e4 + 10;
const int INF = 1e9 + 10;

struct Edge
{
    int to;
    int cost;

    Edge(){};

    Edge(int to, int cost)
    {
        this->to = to;
        this->cost = cost;
    }

    friend bool operator<(const Edge &e1, const Edge &e2)
    {
        return e1.cost > e2.cost;
    }
};

int n, m;
int power[MAXN];
int pos[MAXN];
int dist[MAXN];
vector < Edge > adj[MAXN];
set < int > pows[MAXN];

void read()
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        cin >> pos[i] >> power[i];
        pos[i]++;
    }
}

void build_graph()
{
    for(int i = 1; i <= m; i++)
    {
        pows[pos[i]].insert(power[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                continue;

            int diff = abs(i - j);

            set < int > dels;

            for(int d = 1; d * d <= diff; d++)
            {
                if(diff % d == 0)
                {
                    dels.insert(d);
                    dels.insert(diff / d);
                }
            }

            for(int d : dels)
            {
                int len = diff / d;

                if(pows[i].find(len) != pows[i].end())
                {
                    adj[i].push_back(Edge(j, d));
                    break;
                }
            }
        }
    }
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }

    priority_queue < Edge > pq;

    dist[pos[1]] = 0;

    pq.push(Edge(pos[1], 0));

    while(!pq.empty())
    {
        Edge t = pq.top();
        pq.pop();

        int u = t.to;

        if(u == pos[2])
            break;

        if(t.cost > dist[u])
            continue;

        for(Edge &e : adj[u])
        {
            if(dist[e.to] > dist[u] + e.cost)
            {
                dist[e.to] = dist[u] + e.cost;
                pq.push(Edge(e.to, dist[e.to]));
            }
        }
    }

    if(dist[pos[2]] == INF)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[pos[2]] << endl;
    }
}

int main()
{
    speed();
    read();
    build_graph();
    solve();

	return 0;
}

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