Submission #123918

#	Time	Username	Problem	Language	Result	Execution time	Memory
123918		Mtaylor	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1082 ms	71160 KiB

skyscraper

#include <bits/stdc++.h>

    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl ;

    #define mp make_pair
    #define pb push_back
    #define f first
    #define s second
    #define all(v) (v).begin(),(v).end()


    const int MOD = 1000000007;
    const int N = 1000005;
    const double PI =4*atan(1);
    const double eps = 1e-7;

    ll n,m;
    ll x,y;
    vl tab[N];
    ll p[N];
    ll b[N];
    bool vis[N];
    set <pair<ll,ll> > sss;
    ll ans=-1;

    void bfs(ll u){
      set<pair<ll,pair<ll,ll> > > ss;
		for(auto t:tab[u]){
			ss.insert(mp(0,mp(u,p[t])));
		}
		vis[u]=1;
      pair<ll,pair<ll,ll> > ras;
      while(!ss.empty()){
        ras=*ss.begin();
        ss.erase(ss.begin());
        if(ras.s.f==b[1]){
          ans=ras.f;
          return ;
        }
        if(sss.count(ras.s))continue;
        sss.insert(ras.s);
        //cout << ras.s.f << " " << ras.s.s << endl;
        if(ras.s.s+ras.s.f <n && sss.count(mp(ras.s.s+ras.s.f,ras.s.s))==0){
        	ss.insert(mp(ras.f+1,mp(ras.s.s+ras.s.f,ras.s.s)));
        }
        if(ras.s.f-ras.s.s >=0 && sss.count(mp(ras.s.f-ras.s.s,ras.s.s))==0){
        	ss.insert(mp(ras.f+1,mp(ras.s.f-ras.s.s,ras.s.s)));
        }
        if(vis[ras.s.f])continue;
        for(auto t: tab[ras.s.f]){
          ss.insert(mp(ras.f,mp(ras.s.f,p[t]) ));
        }
        vis[ras.s.f]=1;
      }
    }


   

    int main(){
        ios::sync_with_stdio(0);
        //freopen("easy.txt","r",stdin);
        cin >> n >>m ;
        for(int i=0;i<m;i++){
          cin >> x >> y;
          p[i]=y;
          b[i]=x;
          tab[x].pb(i);
        }
        bfs(b[0]);
        cout << ans;




        return 0;
    }

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