Submission #536023

#TimeUsernameProblemLanguageResultExecution timeMemory
536023PoPularPlusPlusJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
332 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pb(e) push_back(e) #define sv(a) sort(a.begin(),a.end()) #define sa(a,n) sort(a,a+n) #define mp(a,b) make_pair(a,b) #define vf first #define vs second #define ar array #define all(x) x.begin(),x.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const double PI=3.14159265358979323846264338327950288419716939937510582097494459230; bool remender(ll a , ll b){return a%b;} //freopen("problemname.in", "r", stdin); //freopen("problemname.out", "w", stdout); void solve(){ int n , m; cin >> n >> m; int rt = 0; vector<pair<int,int>> adj[n + 1][rt+1]; vector<int> v[n]; int s , e; for(int i = 0; i < m; i++){ int b , p; cin >> b >> p; if(i == 0)s = b; if(i == 1)e = b; if(p <= rt) v[b].pb(p); if(p > rt){ int pos = b , dis = 0; while(pos - p >= 0){ pos -= p; dis++; adj[b][0].pb(mp(pos , dis)); } pos = b; dis = 0; while(pos + p < n){ pos += p; dis++; adj[b][0].pb(mp(pos , dis)); } } } for(int i = 0; i < n; i++){ for(int j = 1; j <= rt; j++){ if(i - j >= 0){ adj[i][j].pb(mp(i-j , 1)); } if(i + j < n){ adj[i][j].pb(mp(i+j , 1)); } } } int dis[n][rt+1]; for(int i = 0; i < n; i++){ for(int j = 0; j <= rt; j++){ dis[i][j] = 1e9; } } priority_queue< pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>> > pq; dis[s][0] = 0; pq.push(mp(0 , mp(s , 0))); while(pq.size()){ int di = pq.top().vf , pos = pq.top().vs.vf , pow = pq.top().vs.vs; //cout << di << ' ' << pos << ' ' << pow << '\n'; pq.pop(); //cout << pos << ' ' << pow << endl; if(dis[pos][pow] < di)continue; if(pow == 0){ for(int i : v[pos]){ pq.push(mp(di , mp(pos , i))); } } for(auto i : adj[pos][pow]){ if(dis[i.vf][pow] > di + i.vs){ dis[i.vf][pow] = di + i.vs; if(pow != 0 && dis[i.vf][0] > di + i.vs){ dis[i.vf][0] = di + i.vs; pq.push(mp(di + i.vs,mp(i.vf , 0))); } pq.push(mp(di + i.vs , mp(i.vf , pow))); } } } cout << (dis[e][0] == 1e9 ? -1 : dis[e][0]) << '\n'; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //int t;cin >> t;while(t--) solve(); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:8:30: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
    8 | #define mp(a,b) make_pair(a,b)
      |                              ^
skyscraper.cpp:27:6: note: 's' was declared here
   27 |  int s , e;
      |      ^
skyscraper.cpp:92:19: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  cout << (dis[e][0] == 1e9 ? -1 : dis[e][0]) << '\n';
      |           ~~~~~~~~^
#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...