Submission #248672

#	Time	Username	Problem	Language	Result	Execution time	Memory
248672		Marlov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	16 ms	20480 KiB

skyscraper

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pi;

#define maxV 30005

long long N,M;
pair<long long,long long> doge[maxV];
map< long long,map<long long,bool> > visited;
//bool visited[maxV][maxV];
queue<long long> cnts[maxV];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(long long i=0;i<M;i++){
        cin>>doge[i].first>>doge[i].second;
        cnts[doge[i].first].push(i);
    }
    //bfs
    queue< pair< long long,pair<long long,long long> > > q;
    q.push(make_pair(0,make_pair(0,doge[0].first)));
    visited[0][doge[0].first]=true;
    while(!q.empty()){
        long long cd=q.front().first;
        long long ci=q.front().second.first;
        long long cl=q.front().second.second;
        q.pop();
        //solution
        if(ci==1){
            cout<<cd<<'\n';
            return 0;
        }
        while(!cnts[cl].empty()){
            q.push(make_pair(cd,make_pair(cnts[cl].front(),cl)));
            cnts[cl].pop();
        }
        if(cl-doge[ci].second>=0&&visited[ci][cl-doge[ci].second]==false){
            q.push(make_pair(cd+1,make_pair(ci,cl-doge[ci].second)));
            visited[ci][cl-doge[ci].second]=true;
        }
        if(cl+doge[ci].second<N&&visited[ci][cl+doge[ci].second]==false){
            q.push(make_pair(cd+1,make_pair(ci,cl+doge[ci].second)));
            visited[ci][cl+doge[ci].second]=true;
        }

    }
    cout<<"-1"<<'\n';
    return 0;
}

/* stuff you should look for
	* long long overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

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