Submission #298527

#	Time	Username	Problem	Language	Result	Execution time	Memory
298527		Genius1506	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	1092 ms	35688 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define dlwlrma ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int> 
#define f first
#define s second
const int mxN = 30002;
int n,m,src,dest,vis[mxN];
set<int>doge[mxN];
vector<pii>chu[mxN];
priority_queue<pii>pq;
int main(){
    dlwlrma
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int b,p;
        cin >> b >> p;
        if(i==0)
            src=b;
        if(i==1)
            dest=b;
        doge[b].insert(p);
    }
    for(int i = 0; i < n; i++){
        for(int next : doge[i]){
            for(int j = i + next, cnt = 1; j < n; j+=next,cnt++){
                chu[i].push_back({j,cnt});
                if(doge[j].find(next)!=doge[j].end())
                    break;
            }
            for(int j = i - next, cnt = 1; j >= 0; j-=next, cnt++){
                chu[i].push_back({j,cnt});
                if(doge[j].find(next)!=doge[j].end())
                    break;
            }
        }
    }
    memset(vis,0x3f,sizeof(vis));
    pq.push({0,src});
    vis[src]=0;
    while(!pq.empty()){
        pii cur = pq.top(); pq.pop();
        int dist = cur.f, node = cur.s;
        if(node == dest){
            cout << dist << "\n";
            return 0;
        }
        for(pii next : chu[node]){
            if(next.s - dist < vis[next.f]){
                vis[next.f]= next.s - dist;
                pq.push({dist+next.s,next.f});
            }
        }
    }
    cout << -1 << "\n";
}

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