Submission #1273053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273053		nthvn	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	2 ms	1860 KiB

skyscraper

#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N=  30005;
int n,m;
pii a[N];
bitset<N> used;
vector<pii> g[N];
vector<int> key[N];

unordered_map<int,int> d[N];

void bfs(){
	deque<pii> dq;
	for(auto &x: key[1]){
		dq.pb({1,x});
		d[1][x] = 0;
	}
	while(!dq.empty()){
		int u = dq.front().fi, k = dq.front().se;
		dq.pop_front();
		for(auto &x: key[u]){
			if(!d[u].count(x)||d[u][x]>d[u][k]){
				d[u][x]= d[u][k];
				dq.push_front({u,x});
			}
		}
		for(auto &e: g[u]){
			int v= e.fi, f= e.se;
			if(f!=k) continue;
			if(!d[v].count(f)||d[v][f]>d[u][f]+1){
				d[v][f] = d[u][f]+1;
				dq.pb({v,f});
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		cin>>a[i].fi>>a[i].se;
		a[i].fi++;
	}
	sort(a+1,a+m+1,[&](pii &a, pii &b){
		if(a.se==b.se) return a.fi<b.fi;
		return a.se < b.se;
	});
	int last =0;
	for(int i=1;i<=m;i++){
		if(last!=a[i].se){
			used =0;
			last =a[i].se;
		}
		int x= a[i].fi, y = a[i].se, c= x%y;
		// cerr<<x<<" "<<y<<"\n";
		if(used[c]) continue;
		used[c]= 1;
		for(int i = x%y; i<=n;i+=y){
			if(i==0) continue;
			if(i-y>0) g[i].pb({i-y,y});
			if(i+y<=n) g[i].pb({i+y,y});
		}
	}
	for(int i=1;i<=m;i++){
		key[a[i].fi].pb(a[i].se);
	}
	bfs();
	int ans = 1e9;
	for(auto &x: d[2]) ans = min(ans, x.se);
	cout<<ans;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:51:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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