Submission #683959

#	Time	Username	Problem	Language	Result	Execution time	Memory
683959		speedyArda	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	263 ms	63236 KiB

skyscraper

#include "bits/stdc++.h"
 
using namespace std;
const int MAXN = 3e4+5;
 
vector< vector < pair<int, int> > > adj(MAXN);
vector< set <  int > > doges(MAXN);
int dp[MAXN];
//map< pair<int, int>, bool > done;
//map< pair<int, int>, int> max_road;
bool visited[MAXN];
int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int goal, begin;
    for(int i = 0; i < m; i++)
    {
        pair<int, int> temp;
        cin >> temp.first >> temp.second;
        if(i == 1)
            goal = temp.first;
        else if(i == 0)
            begin = temp.first;
        doges[temp.first].insert(temp.second);
        //done[{temp.first, temp.second}] = true;

    }
 
    for(int i = 0; i <= n; i++) {
        dp[i] = 1e9;
        //visited[i] = false;
    }

    //visited[begin] = false;
    dp[begin] = 0;
    set< pair<int, int> > curr; 
    curr.insert({0, begin});
    int ans = 1e9;
    for(int i = 0; i < n; i++)
    {
        for(int e : doges[i])
        {
            //cout << i << " " << e << "\n";
            int cnt = 1;
            int currNode = e + i;
            while(currNode < n)
            {
                //cout << i << " " << e << " " << currNode << "\n";
                adj[i].push_back({cnt, currNode});
                if(doges[currNode].find(e) != doges[currNode].end())
                    break;
                cnt++;
                currNode += e;
                
            }

            cnt = 1;
            currNode = i - e;
            while(currNode >= 0)
            {
                
                //cout << i << " " << e << " " << currNode << "\n";
                adj[i].push_back({cnt, currNode});
                if(doges[currNode].find(e) != doges[currNode].end())
                    break;
                cnt++;
                currNode -= e;
                
            }
        }

    }
    while(!curr.empty())
    {
        pair<int, int> node = *(curr.begin());
        int v = node.second;
        curr.erase(curr.begin());
        //int max_road[n];
        visited[v] = true;
        for(pair<int, int> to : adj[v])
        {
            if(dp[to.second] > dp[v] + to.first)
            {
                curr.erase({dp[to.second], to.second});
                dp[to.second] = dp[v] + to.first;
                curr.insert({dp[to.second], to.second});
            }
        }
            
        
       
        
    }
    

   
    ans = dp[goal];
    if(ans >= 1e9)
        ans = -1;
    cout << ans << "\n";
 
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:100:9: warning: 'goal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     ans = dp[goal];
      |     ~~~~^~~~~~~~~~

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