Submission #1186669

#TimeUsernameProblemLanguageResultExecution timeMemory
1186669icebearJakarta Skyscrapers (APIO15_skyscraper)C++20
22 / 100
250 ms327680 KiB
// ~~ icebear love attttt ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebearat" #define index loveat const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 30000 + 5; const int THRESHOLD = 700; int n, m; vector<ii> G[N]; int dist[N][THRESHOLD + 5], index[N], far[N]; vector<int> doges[N]; bool active[N]; struct state { int dist, pos, jump; bool operator > (const state &other) const { return dist > other.dist; } }; priority_queue<state, vector<state>, greater<state>> Q; #define HEAVY_FAR(x) ((x) > THRESHOLD) void init(void) { cin >> n >> m; REP(i, m) { cin >> index[i] >> far[i]; if (HEAVY_FAR(far[i])) { for(int num = 0; index[i] + num * far[i] < n; num++) G[index[i]].emplace_back(index[i] + num * far[i], num); for(int num = 0; index[i] - num * far[i] >= 0; num--) G[index[i]].emplace_back(index[i] - num * far[i], num); far[i] = THRESHOLD + 1; } else doges[index[i]].pb(far[i]); } } void process(void) { memset(dist, 0x3f, sizeof dist); assert(far[0] <= THRESHOLD + 1); dist[index[0]][far[0]] = 0; Q.push({0, index[0], far[0]}); while(!Q.empty()) { int d = Q.top().dist; int pos = Q.top().pos; int jump = Q.top().jump; Q.pop(); assert(pos < n); assert(jump <= THRESHOLD + 1); if (dist[pos][jump] != d) continue; if (pos == index[1]) { cout << d; exit(0); } if (!HEAVY_FAR(jump)) { if (pos + jump < n && minimize(dist[pos + jump][jump], d + 1)) Q.push({d + 1, pos + jump, jump}); if (pos - jump >= 0 && minimize(dist[pos - jump][jump], d + 1)) Q.push({d + 1, pos - jump, jump}); } if (!active[pos]) { for(int dogeJump : doges[pos]) { if (minimize(dist[pos][dogeJump], d)) Q.push({d, pos, dogeJump}); } for(ii x : G[pos]) { int v, w; tie(v, w) = x; int nxt = THRESHOLD + 1; if (minimize(dist[v][nxt], d + w)) Q.push({dist[v][nxt], v, nxt}); } active[pos] = true; } } cout << -1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...