oj.uz

Submission #961845

# Submission time Handle Problem Language Result Execution time Memory
961845 2024-04-12T14:49:35 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 75 ms 178856 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 175116 KB Output is correct
2 Correct 65 ms 174940 KB Output is correct
3 Correct 66 ms 174940 KB Output is correct
4 Correct 66 ms 174940 KB Output is correct
5 Correct 67 ms 175044 KB Output is correct
6 Correct 65 ms 174940 KB Output is correct
7 Correct 65 ms 175116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 174928 KB Output is correct
2 Correct 66 ms 175044 KB Output is correct
3 Correct 64 ms 175112 KB Output is correct
4 Correct 64 ms 174936 KB Output is correct
5 Correct 65 ms 175116 KB Output is correct
6 Correct 65 ms 174928 KB Output is correct
7 Correct 67 ms 175092 KB Output is correct
8 Correct 71 ms 175160 KB Output is correct
9 Correct 66 ms 175272 KB Output is correct
10 Correct 70 ms 175964 KB Output is correct
11 Correct 71 ms 178852 KB Output is correct
12 Correct 70 ms 177780 KB Output is correct
13 Correct 70 ms 177756 KB Output is correct
14 Correct 72 ms 178604 KB Output is correct
15 Correct 71 ms 178512 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 174932 KB Output is correct
2 Correct 65 ms 174868 KB Output is correct
3 Correct 64 ms 174936 KB Output is correct
4 Correct 65 ms 175116 KB Output is correct
5 Correct 67 ms 175116 KB Output is correct
6 Correct 63 ms 174932 KB Output is correct
7 Correct 66 ms 175112 KB Output is correct
8 Correct 65 ms 175180 KB Output is correct
9 Correct 65 ms 175276 KB Output is correct
10 Correct 66 ms 176056 KB Output is correct
11 Correct 73 ms 178772 KB Output is correct
12 Correct 69 ms 177600 KB Output is correct
13 Correct 73 ms 177980 KB Output is correct
14 Correct 71 ms 178520 KB Output is correct
15 Correct 75 ms 178608 KB Output is correct
16 Correct 71 ms 176488 KB Output is correct
17 Incorrect 73 ms 178408 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 174932 KB Output is correct
2 Correct 66 ms 174940 KB Output is correct
3 Correct 67 ms 174936 KB Output is correct
4 Correct 65 ms 175116 KB Output is correct
5 Correct 65 ms 175116 KB Output is correct
6 Correct 64 ms 175088 KB Output is correct
7 Correct 69 ms 174932 KB Output is correct
8 Correct 65 ms 175184 KB Output is correct
9 Correct 67 ms 175192 KB Output is correct
10 Correct 67 ms 175964 KB Output is correct
11 Correct 72 ms 178856 KB Output is correct
12 Correct 68 ms 177756 KB Output is correct
13 Correct 74 ms 177992 KB Output is correct
14 Correct 75 ms 178636 KB Output is correct
15 Correct 71 ms 178608 KB Output is correct
16 Correct 70 ms 176468 KB Output is correct
17 Incorrect 72 ms 178272 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 175116 KB Output is correct
2 Correct 69 ms 174928 KB Output is correct
3 Correct 66 ms 175116 KB Output is correct
4 Correct 68 ms 175264 KB Output is correct
5 Correct 64 ms 174948 KB Output is correct
6 Correct 66 ms 174936 KB Output is correct
7 Correct 68 ms 174936 KB Output is correct
8 Correct 68 ms 175176 KB Output is correct
9 Correct 69 ms 175056 KB Output is correct
10 Correct 67 ms 176052 KB Output is correct
11 Correct 75 ms 178776 KB Output is correct
12 Correct 70 ms 177780 KB Output is correct
13 Correct 68 ms 177748 KB Output is correct
14 Correct 70 ms 178604 KB Output is correct
15 Correct 74 ms 178512 KB Output is correct
16 Correct 66 ms 176492 KB Output is correct
17 Incorrect 72 ms 178416 KB Output isn't correct
18 Halted 0 ms 0 KB -