Submission #259241

#	Time	Username	Problem	Language	Result	Execution time	Memory
259241		shayan_p	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	432 ms	112760 KiB

skyscraper

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e4 + 10;

vector<int> vec[maxn];
bitset<maxn> bs[maxn];
int dis[maxn];
bool done[maxn];
pii p[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++){
	cin >> p[i].F >> p[i].S;
	vec[p[i].F].PB(p[i].S);
    }
    fill(dis, dis + maxn, -1);
    deque< pair<pii, int> > q;
    q.push_back({p[0], 0});
    while(sz(q)){
	int pos = q.front().F.F, p = q.front().F.S, d = q.front().S;
	q.pop_front();
	if(bs[pos][p])
	    continue;
	bs[pos][p] = 1;
	if(done[pos] == 0){
	    dis[pos] = d;
	    for(int x : vec[pos])
		q.push_front({ {pos, x}, d });
	}
	done[pos] = 1;
	if(pos >= p)
	    q.push_back({ {pos - p, p}, d + 1 });
	if(pos + p < n)
	    q.push_back({ {pos + p, p}, d + 1 });
    }
    return cout << dis[p[1].F] << endl, 0;
}

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