Submission #99527

#	Time	Username	Problem	Language	Result	Execution time	Memory
99527		ae04071	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	388 ms	31144 KiB

skyscraper

#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using pii=pair<int,int>;

struct Data{
    int b,p,idx;
    Data() {}
    Data(int b,int p,int idx=0):b(b),p(p),idx(idx){}
    bool operator<(const Data &rhs)const {
        if(p!=rhs.p) return p<rhs.p;
        else if(b%p!=rhs.b%rhs.p) return b%p < rhs.b%rhs.p;
        else return b<rhs.b;
    }
};
int n,m;
vector<Data> arr[30000];
int vis[10000001];

queue<pair<int, Data>> que;

void push(int cost,Data v) {
    if(v.b-v.p>=0 && !vis[v.idx-1]) {
        vis[v.idx-1]=1;
        que.push({cost,Data(v.b-v.p,v.p,v.idx-1)});
    }
    if(v.b+v.p<n && !vis[v.idx+1]) {
        vis[v.idx+1]=1;
        que.push({cost,Data(v.b+v.p,v.p,v.idx+1)});
    }
}
int main() {
    int si,ei;
    vector<Data> ta;
    scanf("%d%d",&n,&m);
    for(int i=0,a,b;i<m;i++) {
        scanf("%d%d",&a,&b);
        ta.push_back(Data(a,b));
        if(i==0) si = a;
        else if(i==1) ei = a;
    }
    sort(ta.begin(),ta.end());
    
    for(int i=0,j=0,c=0;i<m;i=j) {
        for(j=i;j<sz(ta) && ta[i].b%ta[i].p == ta[j].b%ta[j].p && ta[i].p == ta[j].p;j++);
        for(int b=ta[i].b%ta[i].p, k=i;b<n;b+=ta[i].p,c++) {
            while(k<j && b==ta[k].b) {
                arr[b].push_back(Data(b,ta[i].p,c));
                k++;
            }
        }
    }

    que.push({0, Data(si, 0, -1)});
    while(!que.empty()) {
        int cost=que.front().fi;
        Data v=que.front().se;
        que.pop();
        if(v.b==ei) {
            printf("%d\n",cost);
            return 0;
        }
        
        if(v.p!=0) push(cost+1, v);
        while(!arr[v.b].empty()) {
            Data tmp=arr[v.b].back(); arr[v.b].pop_back();
            push(cost+1, tmp);
        }
    }
    puts("-1");
    
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:61:9: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(v.b==ei) {
         ^~

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