Submission #670931

#	Time	Username	Problem	Language	Result	Execution time	Memory
670931		Dan4Life	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	21 ms	36180 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = (int)2e3+10;
const ll LINF = (ll)1e18;
int n, m, ans;
pair<int,int> a[maxn];
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 power){
	Q.push({pos,power}); 
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j < maxn; j++)
			dis[i][j]=LINF, vis[i][j]=0;
	dis[pos][power]=0; vis[pos][power]=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);
	vector<int> ord(m); iota(ord.begin(),ord.end(),0);
	sort(ord.begin(),ord.end(),[&](int i, int j){ return a[i].fi < a[j].fi; });
	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:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |  if(ans==LINF) ans=-1; cout << ans;
      |  ^~
skyscraper.cpp:44:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |  if(ans==LINF) ans=-1; cout << ans;
      |                        ^~~~

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