Submission #1040972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040972		dpsaveslives	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	57 ms	49492 KiB

skyscraper

#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.f < b.f;
}
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;
}

Compilation message (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){
      |                       ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43