제출 #162342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162342		kostia244	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	295 ms	113272 KiB

skyscraper

#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
//using namespace __gnu_pbds;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
const ll mod = 998244353;
//using oset = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 30020;
ll n, m, dist[maxn], s, t;
vi doges[maxn];
bitset<maxn> hs[maxn];
int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	for (int b, p, i = 0; i < m; i++) {
		cin >> b >> p;
		if(!i) s = b;
		if(i==1) t = b;
		if(!hs[b].test(p))doges[b].pb(p), hs[b].set(p, 1);
	}
	priority_queue<pair<int, int>> pq;
	dist[s]=0;
	pq.push({0, s});
	while (!pq.empty()) {
		int u, cst;
		tie(cst, u) = pq.top();
		pq.pop();
		cst *= -1;
		if (cst > dist[u])
			continue;
		if(u==t) {
			cout << cst << '\n';
			return 0;
		}
		for (auto k : doges[u]) {
			for (int v, z =3, i = 1; z&&(u + i * k < n || u - i * k >= 0); i++) {
				v = u + i*k;
				if(v < n){
					if(dist[v] > dist[u] + i) {
						dist[v] = dist[u] + i;
						pq.push({-dist[v], v});
					}
					if(hs[v].test(k))
						z&=1;
				}
				v = u - i * k;
				if(v >= 0){
					if(dist[v] > dist[u] + i) {
						dist[v] = dist[u] + i;
						pq.push({-dist[v], v});
					}
					if(hs[v].test(k))
						z&=2;
				}
			}
		}
	}
	cout << -1;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

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