Submission #882501

#	Time	Username	Problem	Language	Result	Execution time	Memory
882501		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	375 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18 + 7;
void solve(){
    int n, m;
    cin >> n >> m;
    pair < int , int > doge[m];
    vector < int > has[n];
    for(int i = 0;i<m;i++){
        cin >> doge[i].first >> doge[i].second;
        has[doge[i].first].push_back(doge[i].second);
    }
    int edge[n][n];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            edge[i][j] = inf;
        }
    }
    for(int i = 0;i<n;i++){
        sort(has[i].begin() , has[i].end());
        has[i].resize(unique(has[i].begin() , has[i].end()) - has[i].begin());
        for(auto itr : has[i]){
            for(int j = i;j<n;j+=itr){
                edge[i][j] = min(edge[i][j] , (j-i) / itr);
            }
            for(int j = i;j>=0;j-=itr){
                edge[i][j] = min(edge[i][j] , (i-j) / itr);
            }
        }
    }
    priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;
    pq.push({0,doge[0].first});
    int vis[n];
    memset(vis , 0 , sizeof(vis));
    while(pq.size()){
        pair < int , int > tmp = pq.top();
        pq.pop();
        if(vis[tmp.second])continue;
        vis[tmp.second] = 1;
        if(tmp.second == doge[1].first){
            cout << tmp.first << '\n';
            return;
        }
        for(int i = 0;i<n;i++){
            if(edge[tmp.second][i] != inf and vis[i] == 0){
                pq.push({tmp.first + edge[tmp.second][i] , i});
            }
        }
    }
    cout << -1 << '\n';
}
signed main(){  
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
}

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