oj.uz

Submission #512612

# Submission time Handle Problem Language Result Execution time Memory
512612 2022-01-16T13:55:56 Z CaoHuuKhuongDuy Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 3 ms 4172 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e4+9;
const int oo=1e9+9;
typedef pair <int,int> ii;
typedef pair <int,ii> iii;
int can,n,m,a[N],p[N],f[N][176];
bool First[N],check[N][176],doge[N];
vector <int> num[N];
queue <iii> q;
void update(int x,int dist,int val)
{
    if (f[x][dist]>val)
      {
        f[x][dist]=val;
        q.push({val,{x,dist}});
      }
    if (num[x].size()==0||dist==0) return;
}
int solve()
{
    if (p[1]>=can) 
      {
        f[a[1]][0]=0;
        q.push({0,{a[1],0}});
      }
    else 
      {
        f[a[1]][p[1]]=0;
        q.push({0,{a[1],p[1]}});
      }
    int val,x,dist;
    while (!q.empty())
      {
        val=q.front().first;
        x=q.front().second.first;
        dist=q.front().second.second;
        q.pop();
        if (f[x][dist]!=val) continue;
        if (!First[x])
          {
            for (int i=0;i<can;i++)
              if (check[x][i]||i==0) update(x,i,val);
          }
        if (dist!=0)
          {
            if (x+dist<=n) update(x+dist,dist,f[x][dist]+1);
            if (x-dist>=1) update(x-dist,dist,f[x][dist]+1);
          }
        if (First[x]) continue;
        First[x]=true;
        for (int xnew:num[x])
          {
            int dem=0;
            for (int i=x;i<=n;i+=p[xnew])
            {
              update(i,0,val+dem);
              dem++;
            }
            dem=0;
            for (int i=x;i>=1;i-=p[xnew])
            {
              update(i,0,val+dem);
              dem++;
            }
          }
      }
    int res=oo;
    for (int i=0;i<=can;i++)
      res=min(res,f[a[2]][i]);
    if (res==oo) res=-1;
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
   // freopen("test.inp","r",stdin);
    cin>>n>>m;
    can=sqrt(n);
    for (int i=0;i<=n;i++)
      for (int j=0;j<=can;j++)
        f[i][j]=oo;
    for (int i=1;i<=m;i++)
      {
        cin>>a[i]>>p[i];
        doge[a[i]]=true;
        a[i]++;
        if (p[i]>=can) num[a[i]].push_back(i);
        else check[a[i]][p[i]]=true;
      }
    cout<<solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 1016 KB Output is correct
3 Correct 1 ms 1028 KB Output is correct
4 Correct 1 ms 1008 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 1032 KB Output is correct
7 Correct 1 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1008 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 1032 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1228 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1156 KB Output is correct
14 Correct 1 ms 1164 KB Output is correct
15 Correct 1 ms 1156 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1032 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1008 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 2 ms 1228 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1168 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 2 ms 2196 KB Output is correct
18 Correct 2 ms 3532 KB Output is correct
19 Correct 2 ms 3844 KB Output is correct
20 Correct 2 ms 4172 KB Output is correct
21 Correct 2 ms 1612 KB Output is correct
22 Correct 2 ms 3532 KB Output is correct
23 Incorrect 2 ms 3276 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1012 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 1 ms 1228 KB Output is correct
12 Correct 1 ms 1164 KB Output is correct
13 Correct 2 ms 1228 KB Output is correct
14 Correct 1 ms 1168 KB Output is correct
15 Correct 1 ms 1168 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 2 ms 2184 KB Output is correct
18 Correct 2 ms 3532 KB Output is correct
19 Correct 2 ms 3788 KB Output is correct
20 Correct 3 ms 4172 KB Output is correct
21 Correct 1 ms 1612 KB Output is correct
22 Correct 2 ms 3532 KB Output is correct
23 Incorrect 3 ms 3276 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 952 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 1 ms 1288 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1168 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1156 KB Output is correct
16 Correct 1 ms 1292 KB Output is correct
17 Correct 2 ms 2188 KB Output is correct
18 Correct 2 ms 3532 KB Output is correct
19 Correct 2 ms 3788 KB Output is correct
20 Correct 2 ms 4172 KB Output is correct
21 Correct 1 ms 1676 KB Output is correct
22 Correct 2 ms 3532 KB Output is correct
23 Incorrect 2 ms 3276 KB Output isn't correct
24 Halted 0 ms 0 KB -