Submission #883514

#	Time	Username	Problem	Language	Result	Execution time	Memory
883514		SalihSahin	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1062 ms	40952 KiB

skyscraper

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
 
using namespace std;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int N = 3e4 + 5;


int32_t main(){
    ios_base::sync_with_stdio(false), cin.tie();
    int n, m;
    cin>>n>>m;
    vector<int> dudes[N+1];
    int start = 0, finish = 0;
    for(int i = 0; i < m; i++){
        int b, p;
        cin>>b>>p;
        if(i == 0) start = b;
        if(i == 1) finish = b;
        dudes[b].pb(p);
    }
    vector<pair<int, int> > adj[N];

    priority_queue<pair<int, int> > pq;
    vector<int> best(N, inf), vis(N);
    best[start] = 0;
    set<int> st;
    for(int i = 0; i < n; i++) st.insert(i);
    pq.push(mp(0, start));
    
    while(pq.size()){
        int node = pq.top().second;
        int len = pq.top().first * (-1);
        pq.pop();
        
        if(vis[node]) continue;
        vis[node] = 1;
        st.erase(node);

        vector<int> mn(st.size(), inf), num(st.size());
        int ind = 0;

        for(auto i: st){
            num[ind] = i;

            for(auto doge: dudes[node]){
                if(node%doge == i%doge){
                    mn[ind] = min(mn[ind], abs(node - i)/doge);
                }
            }
            ind++;
        }

        for(int i = 0; i < st.size(); i++){
            if(mn[i] != inf) adj[node].pb(mp(num[i], mn[i]));
        }

        for(auto itr: adj[node]){
            if(best[itr.first] > best[node] + itr.second){
                pq.push(mp(-(best[node] + itr.second), itr.first));
                best[itr.first] = best[node] + itr.second;
            }
        }
    }

    if(best[finish] == inf) cout<<-1<<endl;
    else cout<<best[finish]<<endl;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:57:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i = 0; i < st.size(); i++){
      |                        ~~^~~~~~~~~~~
skyscraper.cpp:36:13: warning: unused variable 'len' [-Wunused-variable]
   36 |         int len = pq.top().first * (-1);
      |             ^~~

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