oj.uz

Submission #739463

# Submission time Handle Problem Language Result Execution time Memory
739463 2023-05-10T13:36:22 Z Mauve Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 75 ms 141688 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
#define edge pair<ll, pair<ll,ll> > // une, number ,power
#define cost first
#define num second.first
#define pwr second.second
ll n,m,l,r,i,j,ii,jj,k,x,y,D[30005][172],s,e;
vector< edge > v[30005][172]; // number , power (powergu oroi bol power = 179)
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>l>>r;
        if(i==1) s=l;
        if(i==2) e=l;
        if(r>170)
            for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
                edge a;
                a.num=l+r*j;
                a.pwr=171;
                a.cost=j;
                if(a.num<n) v[l][171].pb(a);
                a.num=l-r*j;
                if(a.num>=0) v[l][171].pb(a);
            }
        else{
            v[l][171].pb({0,{l,r}});
        }
    }
    priority_queue<edge , vector< edge >, greater< edge > > q;
    memset(D,-1,sizeof(D));
    q.push({0,{s,171}});
    while(!q.empty()){
        ll une, nmbr, power;
        une=q.top().cost;
        nmbr=q.top().num;
        power=q.top().pwr;
        q.pop();
        if(D[nmbr][power]==-1){
            D[nmbr][power]=une;
            for(edge no : v[nmbr][power]) if(D[no.num][no.pwr]==-1) q.push({une+no.cost,{no.num,no.pwr}});
            if(power!=171){
                ll poo=nmbr+power,pp=nmbr-power;
                if(D[nmbr][171]==-1) q.push({une,{nmbr,171}});
                if(poo<n && D[poo][power]==-1) q.push({++une,{poo,power}});
                if(pp>=0 && D[pp][power]==-1) q.push({une,{pp,power}});
            }
        }
    }
    cout<<D[e][171];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 141644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 141652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 141628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 141644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 141688 KB Output isn't correct
2 Halted 0 ms 0 KB -