Submission #1192764

#TimeUsernameProblemLanguageResultExecution timeMemory
1192764GrayJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
162 ms327680 KiB
#include <algorithm> #include <bits/stdc++.h> #include <cassert> #include <vector> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define ff first #define ss second #define ln "\n" #define mp make_pair #define pb push_back #define INF (ll)1e18 ll MOD = 1e9+7; struct Fenwick{ vector<ll> pref, suff; ll n, offs; Fenwick(ll N){ n=N+20; offs=10;; pref.resize(n+1); suff.resize(n+1); } void add(ll i, ll x){ i+=offs; ll ai = i; for (; i<=n; i+=(-i&i)) pref[i]+=x; for (i=ai; i; i-=(-i&i)) suff[i]+=x; } ll get_pref(ll i){ i+=offs; ll res=0; for (; i; i-=(-i&i)) res+=pref[i]; return res; } ll get_suff(ll i){ i+=offs; ll res=0; for (; i<=n; i+=(-i&i)) res+=suff[i]; return res; } }; void solve(){ ll n, m; cin >> n >> m; vector<vector<pair<ll, ll>>> avail(n); vector<pair<ll, ll>> d(m); for (ll i=0; i<m; i++){ ll x, p; cin >> x >> p; d[i] = {x, p}; avail[x].push_back({p, i}); } vector<vector<ll>> vis(n, vector<ll>(n+1)); vector<ll> dist(n, INF); queue<tuple<ll, ll, ll>> que; que.push({0, d[0].ff, 0}); while (!que.empty()){ auto [w, x, i]=que.front(); que.pop(); if (vis[x][d[i].ss]) continue; vis[x][d[i].ss]=1; dist[i]=min(dist[i], w); if (x-d[i].ss>=0 and !vis[x-d[i].ss][d[i].ss]) que.push({w+1, x-d[i].ss, i}); if (x+d[i].ss<n and !vis[x+d[i].ss][d[i].ss]) que.push({w+1, x+d[i].ss, i}); for (auto [p, ind]:avail[x]){ dist[ind]=min(dist[ind], w); if (x-d[ind].ss>=0 and !vis[x-d[ind].ss][d[ind].ss]) que.push({w+1, x-d[ind].ss, ind}); if (x+d[ind].ss<n and !vis[x+d[ind].ss][d[ind].ss]) que.push({w+1, x+d[ind].ss, ind}); } } cout << (dist[1]!=INF?dist[1]:-1) << ln; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL auto start = chrono::high_resolution_clock::now(); #endif #ifndef LOCAL freopen("balancing.in", "r", stdin); freopen("balancing.out", "w", stdout); #endif ll testc=1; // cin >> testc; for (ll __c=1; __c<=testc; __c++) solve(); #ifdef LOCAL auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start); cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl; #endif }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen("balancing.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("balancing.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...