oj.uz

Submission #961843

# Submission time Handle Problem Language Result Execution time Memory
961843 2024-04-12T14:48:24 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 100 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

#ifdef sus
const int N=100, S=3;
#else
const int N=3e4+10, S=300;
#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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -