Submission #41515

#TimeUsernameProblemLanguageResultExecution timeMemory
41515wzyJakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
23 ms21848 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define mp make_pair #define pb push_back #define pii pair<int,int> vector<pii> adj[300005]; int n, m; set<int> p[300005]; long long d[300005]; int32_t main(){ scanf("%lld%lld" , &n, &m); for(int i = 0 ; i <m ; i ++){ int b, x; scanf("%lld%lld" , &b , &x); p[b].insert(x); } for(int i = 0 ; i < n; i++){ for(auto t : p[i]){ for(int j = 1 ; j*t + i < n ; j++){ adj[i].pb(pii(j , j*t+i)); if(p[j*t + i].count(t)) break; } for(int j = 1 ; i - j*t >=0 ; j++){ adj[i].pb(pii(j , i-j*t)); if(p[i - j*t].count(t)) break; } } } priority_queue<pii , vector<pii> , greater<pii> > pq; pq.push(pii(0 , 0)); for(int i = 0 ; i< n; i++) d[i] = (long long) 1e18; d[0] = 0; while(!pq.empty()){ pii u = pq.top(); pq.pop(); if(d[u.S] != u.F) continue; d[u.S] = u.F; for(int i = 0 ; i < adj[u.S].size() ; i++){ pii v = adj[u.S][i]; if(d[v.S] > u.F + v.F){ d[v.S] = u.F + v.F; pq.push(pii(u.F + v.F , v.S)); } } } if(d[1] == (int) 1e18) printf("%lld\n" , -1LL); else{ printf("%lld\n" , d[1]); } }

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[u.S].size() ; i++){
                     ^
skyscraper.cpp:15:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" ,  &n,  &m);
                              ^
skyscraper.cpp:18:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld" , &b , &x);
                              ^
#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...