oj.uz

Submission #1096058

# Submission time Handle Problem Language Result Execution time Memory
1096058 2024-10-03T16:20:42 Z alexdd Climbers (RMI18_climbers) C++17
0 / 100
 800 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_STARI = 6300000;
const long long INF = 1e18;
vector<pair<pair<int,int>,pair<int,int>>> edges;

vector<pair<int,int>> con[MAX_STARI];
long long dist[MAX_STARI];

void add_edge(int v1, int m1, int v2, int m2)
{
    edges.push_back({{v1,m1},{v2,m2}});
}
priority_queue<pair<long long,int>> pq;
map<pair<int,int>,int> mp,nrm;
//v - varf, m - muchie
int n,p[5005],cate;
void normalizare()
{
    for(auto [x,y]:edges)
    {
        mp[x]++;
        mp[y]++;
    }
    for(auto it:mp)
        if(it.second)
        {
            nrm[it.first]=++cate;
            //cerr<<it.first.first<<" "<<it.first.second<<"  zzz\n";
        }

}
void afis(int v, int m)
{
    cerr<<"in varful "<<v<<" si pe dreapta "<<m<<" avem "<<dist[nrm[{v,m}]]<<"\n";
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    assert(p[1]==0);
    assert(p[n]==0);
    for(int v=1;v<=n;v++)
    {
        for(int m=1;m<n;m++)
        {
            if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
                continue;
            for(int newv:{v-1,v+1})
            {
                if(newv>=1 && newv<=n && min(p[m],p[m+1]) <= p[newv] && p[newv] <= max(p[m],p[m+1]))
                {
                    add_edge(v,m,newv,m);
                }
            }

            if(p[v] == p[m] && m-1>0)
            {
                add_edge(v,m,v,m-1);
            }
            if(p[v] == p[m+1] && m+1<n)
            {
                add_edge(v,m,v,m+1);
            }

            if(p[v] == p[m])
            {
                if(v<n) add_edge(v,m,m,v);
                if(v>1) add_edge(v,m,m,v-1);
            }
            if(p[v] == p[m+1])
            {
                if(v<n) add_edge(v,m,m+1,v);
                if(v>1) add_edge(v,m,m+1,v-1);
            }
            if(v+1<n && min(p[v],p[v+1]) <= p[m] && p[m] <= max(p[v],p[v+1]))
            {
                add_edge(v,m,m,v);
            }
            if(v-1>0 && min(p[v],p[v-1]) <= p[m] && p[m] <= max(p[v],p[v-1]))
            {
                add_edge(v,m,m,v-1);
            }
        }
    }
    mp[{n,1}]++;
    mp[{1,n-1}]++;
    normalizare();
    for(auto [x,y]:edges)
    {
        int a = nrm[x], b = nrm[y];
        con[a].push_back({b,abs(p[x.first]-p[y.first])});
        con[b].push_back({a,abs(p[x.first]-p[y.first])});
    }
    for(int i=1;i<=cate;i++)
        dist[i]=INF;
    dist[nrm[{n,1}]]=0;
    dist[nrm[{1,n-1}]]=0;
    pq.push({0,nrm[{n,1}]});
    pq.push({0,nrm[{1,n-1}]});
    while(!pq.empty())
    {
        long long cdist = -pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        if(dist[nod]!=cdist)
            continue;
        //cerr<<nod<<" new dist "<<dist[nod]<<"\n";
        for(auto [adj,c]:con[nod])
        {
            if(cdist + c < dist[adj])
            {
                dist[adj] = cdist + c;
                pq.push({-dist[adj],adj});
            }
        }
    }
    long long rez=INF;
    for(int m=1;m<n;m++)
    {
        rez = min(rez, dist[nrm[{m,m}]]);
        rez = min(rez, dist[nrm[{m+1,m}]]);
    }
    /*for(int v=1;v<=n;v++)
        for(int m=1;m<n;m++)
        {
            if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
                continue;
            afis(v,m);
        }*/
    assert(rez<INF);
    cout<<rez;
    return 0;
}
/*
7
0 10 1 20 5 10 0

*/

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 176 ms 306332 KB Execution killed with signal 6
2 Runtime error 216 ms 319688 KB Execution killed with signal 6
3 Runtime error 783 ms 475640 KB Execution killed with signal 6
4 Execution timed out 1075 ms 374696 KB Time limit exceeded
5 Execution timed out 1096 ms 506536 KB Time limit exceeded

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 304724 KB Execution killed with signal 6
2 Runtime error 172 ms 305236 KB Execution killed with signal 6
3 Runtime error 169 ms 309540 KB Execution killed with signal 6
4 Runtime error 178 ms 306940 KB Execution killed with signal 6
5 Runtime error 245 ms 329536 KB Execution killed with signal 6

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 309924 KB Execution killed with signal 6
2 Runtime error 309 ms 341676 KB Execution killed with signal 6
3 Execution timed out 1089 ms 296464 KB Time limit exceeded
4 Runtime error 429 ms 524288 KB Execution killed with signal 9
5 Runtime error 434 ms 524288 KB Execution killed with signal 9
6 Runtime error 452 ms 524288 KB Execution killed with signal 9
7 Runtime error 443 ms 524288 KB Execution killed with signal 9
8 Runtime error 446 ms 524288 KB Execution killed with signal 9
9 Runtime error 429 ms 524288 KB Execution killed with signal 9
10 Runtime error 394 ms 524288 KB Execution killed with signal 9