Submission #961845

#	Time	Username	Problem	Language	Result	Execution time	Memory
961845		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	75 ms	178856 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#ifdef sus
const int N=100, S=3;
#else
const int N=3e4+10, S=100;
#endif
int n, m, b[N], p[N], heavy[N];
vector<pair<int, int>> g1[N];
int f1[N];
int f2[N][S+10];
vector<pair<pair<int, int>, int>> g2[N][S+10];
vector<pair<int, int>> vv[N*S];
int vis[N][S+10];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i) cin >> b[i] >> p[i], heavy[i]=p[i]>=S, ++b[i];
   for (int i=1; i<=m; ++i) if (heavy[i]){
      for (int l=b[i]-p[i], r=b[i]+p[i], cnt=1; l>=1 || r<=n; l-=p[i], r+=p[i], ++cnt){
         if (l>=1) g1[b[i]].emplace_back(l, cnt);
         if (r<=n) g1[b[i]].emplace_back(r, cnt);
      }
   }
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   memset(f1, 0x3f, sizeof f1);
   pq.emplace(f1[b[1]]=0, b[1]);
   while (pq.size()){
      int u=pq.top().second, d=pq.top().first;
      pq.pop();
      if (f1[u]!=d) continue;
      for (auto &e:g1[u]){
         int v=e.first, w=e.second;
         if (f1[v]>d+w) pq.emplace(f1[v]=d+w, v);
      }
   }
   for (int i=1; i<=m; ++i) if (!heavy[i]){
      for (int j=1; j<=S; ++j) if (j!=p[i]) g2[b[i]][j].push_back({{b[i], p[i]}, 0});
   }
   for (int i=1; i<=n; ++i) for (int j=1; j<=S; ++j){
      if (i-j>=1) g2[i][j].push_back({{i-j, j}, 1});
      if (i+j<=n) g2[i][j].push_back({{i+j, j}, 1});
   }
   for (int i=1; i<=m; ++i) if (!heavy[i] && f1[b[i]]<N*S) vv[f1[b[i]]].emplace_back(b[i], p[i]);
   memset(vis, -1, sizeof vis);
   memset(f2, 0x3f, sizeof f2);
   queue<pair<int, int>> q1, q2;
   for (int i=0; i<N*S; ++i){
      for (auto &j:vv[i]) if (f2[j.first][j.second]!=i) q1.push(j), f2[j.first][j.second]=i;
      while (q1.size()){
         auto u=q1.front(); q1.pop();
         for (auto &e:g2[u.first][u.second]){
            auto v=e.first; int w=e.second;
            if (f2[v.first][v.second]>f2[u.first][u.second]+w){
               f2[v.first][v.second]=f2[u.first][u.second]+w;
               if (w){
                  q2.push(v);
               }else{
                  q1.push(v);
               }
            }
         }
      }
      q2.swap(q1);
      while (q2.size()) q2.pop();
   }
   int ans=f1[b[2]];
   for (int i=1; i<=S; ++i) ans=min(ans, f2[b[2]][i]);
   if (ans>1e9) ans=-1;
   cout << ans << '\n';
   return 0;
}

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