제출 #1040969

#제출 시각아이디문제언어결과실행 시간메모리
1040969dpsaveslivesJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
20 ms16476 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int MAXN = 3e4; const int MAX = 5e5; vector<pair<int,int>> power[MAXN+1]; //power[i] saves the doges with the power i int l[MAXN+1], r[MAXN+1]; //do it for the index vector<int> adj[MAXN+1]; vector<int> q[MAX+1]; int dp[MAXN+1]; int val; bool cmp(pair<int,int> a, pair<int,int> b){ if(a.f % val != b.f % val) return a.f%val < b.f % val; return a.s < b.s; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,M; cin >> N >> M; //number of skyscrapers, number of doges vector<pair<int,int>> doges(M); set<pair<int,int>> uni; for(int i = 0;i<M;++i){ cin >> doges[i].f >> doges[i].s; if(uni.find({doges[i].f,doges[i].s}) != uni.end()){ continue; } uni.insert({doges[i].f,doges[i].s}); power[doges[i].s].push_back({doges[i].f,i}); //save the ones with the same power together -> building and index adj[doges[i].f].push_back(i); } for(int i = 1;i<=MAXN;++i){ if(power[i].size() == 0) continue; val = i; sort(power[i].begin(),power[i].end(),cmp); l[power[i][0].s] = power[i][0].f%i; for(int j = 0;j<power[i].size()-1;++j){ if(power[i][j].f % i == power[i][j+1].f % i){ r[power[i][j].s] = power[i][j+1].f; l[power[i][j+1].s] = power[i][j].f; } else{ r[power[i][j].s] = N-1; l[power[i][j+1].s] = power[i][j+1].f%i; } } r[power[i].back().s] = N-1; } q[0].push_back(doges[0].f); fill(dp,dp+N,(1<<30)); for(int i = 0;i<=MAX;++i){ while(!q[i].empty()){ int u = q[i].back(); q[i].pop_back(); if(dp[u] != (1<<30)) continue; dp[u] = i; for(auto v : adj[u]){ for(int j = l[v];j <= r[v];j += doges[v].s){ int cur = abs(u-j)/doges[v].s; if(cur+i < dp[j]){ q[cur+i].push_back(j); } } } } } if(dp[doges[1].f] == (1<<30)){ cout << -1 << "\n"; } else{ cout << dp[doges[1].f] << "\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0;j<power[i].size()-1;++j){
      |                       ~^~~~~~~~~~~~~~~~~~
#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...