Submission #786120

#TimeUsernameProblemLanguageResultExecution timeMemory
786120makanhuliaJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1095 ms31068 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll MAXN = 3e4 + 5; ll n, m, ans = -1, awal, tujuan; vector<ll> baris[MAXN]; // bool visited[MAXN][MAXN]; map<pll, bool> visited; void bfs() { queue<pair<pll, ll>> que; // {{Idx Baris, Lompat}, Dist} for (int i = 0; i < baris[awal].size(); ++i) { que.push({{awal, baris[awal][i]}, 0}); } while(!que.empty()) { pair<pll, ll> now = que.front(); // {{Idx Baris, Lompat}, Dist} que.pop(); if (visited[now.first]) { continue ; } visited[now.first] = true; if (now.first.first == tujuan) { ans = now.second; return ; } ll lompat = now.first.second; ll nxt = now.first.first + lompat; if (nxt < n && !visited[{nxt, lompat}]) { que.push({{nxt, lompat}, now.second+1}); } nxt = now.first.first - lompat; if (nxt >= 0 && !visited[{nxt, lompat}]) { que.push({{nxt, lompat}, now.second+1}); } vector<ll> barisNow = baris[now.first.first]; for (int i = 0; i < barisNow.size(); ++i) { lompat = barisNow[i]; nxt = now.first.first + lompat; if (nxt < n && !visited[{nxt, lompat}]) { que.push({{nxt, lompat}, now.second+1}); } nxt = now.first.first - lompat; if (nxt >= 0 && !visited[{nxt, lompat}]) { que.push({{nxt, lompat}, now.second+1}); } } } } int main(){ cin >> n >> m; for (int i = 0; i < m; ++i) { ll tmpa, tmpb; cin >> tmpa >> tmpb; baris[tmpa].push_back(tmpb); if (i == 0) { awal = tmpa; } else if (i == 1) { tujuan = tmpa; } } bfs(); cout << ans << "\n"; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void bfs()':
skyscraper.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (int i = 0; i < baris[awal].size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < barisNow.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...