Submission #670933

#	Time	Username	Problem	Language	Result	Execution time	Memory
670933		Dan4Life	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	77 ms	38060 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
using ll = long long;
using pii = pair<int,int>;

const int maxn = (int)2e3+10;
const ll LINF = (ll)1e18;
int n, m, ans;
pair<int,int> a[30010];
vector<pii> adj[maxn];
queue<pair<int,int>> Q; 
vector<int> doge[maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn];

void chk(int s, int p, int s2, int p2){
	if(s>=n or s<0 or vis[s][p]) return;
	vis[s][p] = 1; dis[s][p] = dis[s2][p2]+1; Q.push({s,p});
}

void bfs(int pos, int po){
	Q.push({pos,po}); 
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j < maxn; j++)
			dis[i][j]=LINF, vis[i][j]=0;
	dis[pos][po]=0; vis[pos][po]=1;
	while(!Q.empty()){
		int s = Q.front().fi, p = Q.front().se; Q.pop();
		chk(s+p,p,s,p), chk(s-p,p,s,p);
		for(auto u : doge[s]) chk(s+u,u,s,p), chk(s-u,u,s,p);
	}
}

int32_t main() {
	cin >> n >> m; ans = LINF;
	for(int i = 0; i < m; i++) cin >> a[i].fi >> a[i].se, doge[a[i].fi].pb(a[i].se);
	bfs(a[0].fi, a[0].se);
	for(int i = 1; i <= 2000; i++) ans = min(ans, dis[a[1].fi][i]);
	if(ans==LINF) ans=-1; cout << ans;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:43:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |  if(ans==LINF) ans=-1; cout << ans;
      |  ^~
skyscraper.cpp:43:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |  if(ans==LINF) ans=-1; cout << ans;
      |                        ^~~~

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