Submission #316733

#	Time	Username	Problem	Language	Result	Execution time	Memory
316733		uno	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	3 ms	640 KiB

skyscraper

//
// Created by bg Koh on 2020/10/21.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

int N, M;
vector<vector<int>> jump;
vector<int> discovered;
vector<unordered_map<int,int>> adjList;

int dfs(int startBuild, int jmp, int time, unordered_map<int, int>& soFar, int dir )
{
    if (startBuild >= N || startBuild < 0)
        return 0;

    if (soFar.find(startBuild) != end(soFar)) {
        if (soFar[startBuild] > time)
            soFar[startBuild] = time;
    } else {
        soFar.emplace(startBuild, time);
    }
    dfs(startBuild+((dir == 1) ? jmp:-jmp), jmp, time+1, soFar, dir);
    return 1;
}

void makeGraph()
{
    for (int i=0; i<N; ++i) {
        for (int j : jump[i]) {
            unordered_map<int, int> tmp;
            dfs(i+j, j, 1, adjList[i], 1); //right
            dfs(i-j, j, 1, adjList[i], 0); //left
#if 0
            cout << "\n\n" << i << " building:" << endl;
            for (auto& k : adjList[i]) {
                cout << k.first << ":" << k.second << endl;
            }
#endif
        }
    }
}

int firstDogeLoc = 0, firstJump = 0;
int secondDogeLoc= 0, secondJump = 0;
void input()
{
    cin >> N >> M;
    jump = vector<vector<int>>(N,vector<int>());

    cin >> firstDogeLoc >> firstJump;
    jump[firstDogeLoc].emplace_back(firstJump);

    cin >> secondDogeLoc >> secondJump;
    jump[secondDogeLoc].emplace_back(secondJump);

    for (int i=2; i<M; ++i) {
        int start, j;
        cin >> start >> j;
        jump[start].emplace_back(j);
    }
    adjList = vector<unordered_map<int, int>>(N, unordered_map<int,int>());
}

#define INF (int)2e9

vector<int> shortTime;
int dijkstra()
{
    shortTime = vector<int>(N, (int)2e9);
    vector<bool> visited(N, false);
    
    shortTime[0] = 0;
    while (true) {
        int here = INF;
        int distHere = INF;
        for (int i=0; i<N; ++i) {
            if (shortTime[i] < distHere && !visited[i]) {
                here = i;
                distHere = shortTime[i];
            }
        }
        if (distHere == INF)
            break;
        
        if (here == secondDogeLoc)
            return shortTime[here];
        
        visited[here] = true;
        
        for (auto [there, dist] : adjList[here]) {
            int distThere = distHere + dist;
            if (!visited[there] && shortTime[there] > distThere) {
                shortTime[there] = distThere;
            }
        }
    }
    
    return -1;
    //return -1;
}

int main()
{
    cout << "Hello world" << endl;
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    freopen("input.txt","r",stdin);
    input();
    makeGraph();
    cout << dijkstra() << endl;

#if 0
    unordered_map<int,int> test;
    //dfs(2, 2, 1, test, 1);
    dfs(4, 2, 1, test, 0);

    for (auto& i : test) {
        cout << i.first << ":" << i.second << endl;
    }
#endif
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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