Submission #874495

#	Time	Username	Problem	Language	Result	Execution time	Memory
874495		arashMLG	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1051 ms	225320 KiB

skyscraper

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

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

const int N = 3e4 + 10;
const int M = 3e4 + 10;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)
//#define int         short

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

int n,m;
vector<int> here[N];
bool vis[N];
vector<bool> mark[M],mk[M];
deque<pair<pii,int>> dq;
//int dist[M][N];
int b[M],p[M];

void bfs() {
	mark[0][b[0]] = 1;
	dq.push_front({{0,b[0]},0});
	mk[p[0]][b[0]%p[0]] = 1;
	while(sz(dq)) {
		auto [sex,d] = dq.front(); dq.pop_front();
		auto [id,pos] = sex;
		//debug((int)id,(int)pos);
		if(id == 1) {
			kill(d);
		}
		mk[p[id]][b[id] %p[id]] = 1;
		if(!vis[pos]) {
			for(int x : here[pos]) {
				if(!mark[x][pos]) {
					mark[x][pos] = 1;
					if(x == 1) kill(d);
					if(!mk[p[x]][b[x]%p[x]])
						dq.push_front({{x,pos},d});
				}
			}
			vis[pos] = true;
		}
		// front
		if(pos+ p[id] < n && !mark[id][pos + p[id]]) {
			mark[id][pos + p[id]] = true;
			//dist[id][pos + p[id]] = dist[id][pos] + 1;
			dq.push_back({{id,pos+p[id]},d+1});
		}
		// back
		if(pos- p[id] >=0 && !mark[id][pos - p[id]]) {
			mark[id][pos - p[id]] = true;
			//dist[id][pos - p[id]] = dist[id][pos] + 1;
			dq.push_back({{id,pos-p[id]},d+1});
		}
	}
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int i = 0 ;i < M; i ++) {
    	mark[i].resize(M);
    	mk[i].resize(M);
    }
	cin>>n>>m;
	for(int i = 0 ; i <m; i++) {
		cin>>b[i]>>p[i];
		here[b[i]].pb(i);
	}
	bfs();
	kill(-1);
	return 0;
}

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