제출 #259239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259239		shayan_p	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1097 ms	69980 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;

set<int> st[maxn];
set<int> calced[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;
	st[p[i].F].insert(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(calced[pos].count(p))
	    continue;
	calced[pos].insert(p);
	if(done[pos] == 0){
	    dis[pos] = d;
	    for(int x : st[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: 0 / 43