Submission #21975

#TimeUsernameProblemLanguageResultExecution timeMemory
21975HiasatJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
333 ms113844 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> plli; typedef pair<double, double> pdd; typedef pair<string, int> psi; const int MOD = 1e9 + 7; const ll oo = 1e15; typedef long long ll; int n , m; pii d[30010]; bitset<30010> vis[30010]; vector<int> dogs[30010]; int main() { //freopen("input.txt","r",stdin); scanf("%d%d",&n,&m); for (int i = 0; i < m; ++i){ scanf("%d%d",&d[i].first,&d[i].second); dogs[d[i].first].push_back(d[i].second); } for (int i = 1; i <= n; ++i){ sort(dogs[i].begin(),dogs[i].end()); dogs[i].resize(unique(dogs[i].begin(),dogs[i].end()) - dogs[i].begin()); } deque< pair<int , pii > > q; vis[d[0].first][d[0].second] = 1; q.push_front(make_pair(0,make_pair(d[0].first,d[0].second))); while(!q.empty()){ pair<int , pii > src = q.front(); if(src.second.first == d[1].first){ printf("%d\n", src.first); return 0; } q.pop_front(); for (int i = 0; i < dogs[src.second.first].size(); ++i){ int nw = dogs[src.second.first][i]; if(vis[src.second.first][nw]) continue; vis[src.second.first][nw] = 1; q.push_front(make_pair(src.first,make_pair(src.second.first,nw))); } for(int i = -1 ; i <= 1 ; i+= 2){ int nw = src.second.first + src.second.second* i; if(nw < 0 || nw >= n) continue; if(vis[nw][src.second.second]) continue; vis[nw][src.second.second]=1; q.push_back(make_pair(1 + src.first,make_pair(nw,src.second.second))); } } puts("-1"); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dogs[src.second.first].size(); ++i){
                     ^
skyscraper.cpp:29:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
skyscraper.cpp:31:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&d[i].first,&d[i].second);
                                         ^
#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...