oj.uz

Submission #207105

# Submission time Handle Problem Language Result Execution time Memory
207105 2020-03-06T13:28:25 Z istlemin Climbers (RMI18_climbers) C++14
90 / 100
 800 ms 3832 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

ll n;
vi h;

ll lower(ll s){
    if(h[s]<h[s+1]) return s;
    else return s+1;
}
ll upper(ll s){
    if(h[s]<h[s+1]) return s+1;
    else return s;
}



pair<ll, pii> makeEdge(ll v,pii newNode){
    return {abs(h[v]-h[newNode.first]),newNode};
}

vector<pair<ll,pii>> edges(pii node){
    auto [v,s] = node;
    vector<pair<ll,pii>> ret;

    if(h[v+1]<h[v]){
        ll mnS = min(h[s],h[s+1]);
        if(mnS>=h[v+1])
            ret.emplace_back(makeEdge(v,pii({lower(s),v})));
        if(mnS<=h[v+1])
            ret.emplace_back(makeEdge(v,pii({v+1,s})));
        if(mnS>=h[v-1])
            ret.emplace_back(makeEdge(v,pii({lower(s),v-1})));
        if(mnS<=h[v-1])
            ret.emplace_back(makeEdge(v,pii({v-1,s})));
    } else {
        ll mxS = max(h[s],h[s+1]);
        if(mxS<=h[v+1])
            ret.emplace_back(makeEdge(v,pii({upper(s),v})));
        if(mxS>=h[v+1])
            ret.emplace_back(makeEdge(v,pii({v+1,s})));
        if(mxS<=h[v-1])
            ret.emplace_back(makeEdge(v,pii({upper(s),v-1})));
        if(mxS>=h[v-1])
            ret.emplace_back(makeEdge(v,pii({v-1,s})));
    }

    if(h[v]==h[s]) {
        ret.emplace_back(makeEdge(v,pii({s,v})));
        ret.emplace_back(makeEdge(v,pii({s,v-1})));
    }
    if(h[v]==h[s+1]) {
        ret.emplace_back(makeEdge(v,pii({s+1,v})));
        ret.emplace_back(makeEdge(v,pii({s+1,v-1})));
    }

    //cout<<v<<" "<<s<<": ";
    //trav(r,ret) cout<<"("<<r.second.v<<","<<r.second.s<<") ";
    //cout<<endl;
    sort(all(ret));
    ret.erase(unique(all(ret)),ret.end());
    return ret;
}

bool invalid(pii node){
    auto [v,s] = node;
    return v==0||v==n-1||s==0||s==n-2;
}


int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    srand(1);

    cin>>n;
    vi htemp;
    rep(i,0,n) {
        ll x;
        cin>>x;
        //x = rand()%10;
        //if(i==0||i==n-1) x = 0;
        //cout<<x<<" ";
        if(!htemp.size()||htemp.back()!=x) htemp.push_back(x);
    }
    //cout<<endl;
    h.push_back(1e9);
    h.push_back(0);
    rep(i,1,htemp.size()-1){
        if((htemp[i]<htemp[i-1])==(htemp[i]<htemp[i+1])){
            h.push_back(htemp[i]);
        }
    }
    h.push_back(0);
    h.push_back(1e9);

    //trav(hi,h) cout<<hi<<" ";
    //cout<<endl;

    n = h.size();

    priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>> q;
    vector<vector<bool>> seen(n,vector<bool>(n));
    q.emplace(0,pii({1,n-3}));
    while(q.size()){
        ll d = q.top().first;
        pii V = q.top().second;
        q.pop();
        //cout<<d<<": "<<V.v<<" "<<V.s<<endl;
        if(seen[V.first][V.second]||invalid(V)) continue;
        seen[V.first][V.second] = true;


        if(V.first==V.second||V.first-1==V.second){
            cout<<d<<endl;
            return 0;
        }
        trav(e,edges(V)){
            if(seen[e.second.first][e.second.second]||invalid(e.second)) continue;
            q.emplace(d+e.first,e.second);
        }
    }
    assert(false);
}

Compilation message

climbers.cpp: In function 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > > edges(pii)':
climbers.cpp:34:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [v,s] = node;
          ^
climbers.cpp: In function 'bool invalid(pii)':
climbers.cpp:77:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [v,s] = node;
          ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 9 ms 504 KB Output is correct
4 Correct 24 ms 1656 KB Output is correct
5 Correct 76 ms 3832 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct

Subtask #3
40.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 411 ms 832 KB Output is correct
4 Correct 532 ms 1740 KB Output is correct
5 Correct 792 ms 1656 KB Output is correct
6 Correct 769 ms 2632 KB Output is correct
7 Execution timed out 843 ms 2656 KB Time limit exceeded
8 Correct 598 ms 3448 KB Output is correct
9 Correct 770 ms 3680 KB Output is correct
10 Execution timed out 881 ms 3576 KB Time limit exceeded