Submission #762534

#	Time	Username	Problem	Language	Result	Execution time	Memory
762534		alexander707070	Sky Walking (IOI19_walk)	C++14	24 / 100	3337 ms	894316 KiB

walk

#include<bits/stdc++.h>
#define MAXN 2000007
using namespace std;

const long long inf=1e16;

int n,m,z,minv,last,j,h[MAXN]; 
map< pair<int,int>, int > mp;
vector<int> w[MAXN],poss;
vector< pair<int,int> > v[MAXN];
long long dist[MAXN];
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > q; 
bool vis[MAXN];

void add_edge(int x,int y,int c){
    v[x].push_back({y,c});
    v[y].push_back({x,c});
}

void dijkstra(){
    for(int i=1;i<=z;i++){
        dist[i]=inf;
    }

    dist[1]=0;
    q.push({0,1});
    
    while(!q.empty()){
        minv=q.top().second;
        q.pop();

        if(vis[minv])continue;
        vis[minv]=true;

        for(int i=0;i<v[minv].size();i++){
            if(vis[v[minv][i].first] or dist[v[minv][i].first]<dist[minv]+v[minv][i].second)continue;
            dist[v[minv][i].first]=dist[minv]+v[minv][i].second;
            q.push({dist[v[minv][i].first],v[minv][i].first});
        }
    }
}

int tree[400007];

int best(int x,int y){
    if(x==-1)return y;
    if(y==-1)return x;

    if(h[x]>h[y])return x;
    return y;
}

void build(int v,int l,int r){
    if(l==r){
        tree[v]=l;
    }else{
        int tt=(l+r)/2;
        build(2*v,l,tt);
        build(2*v+1,tt+1,r);
        tree[v]=best(tree[2*v],tree[2*v+1]);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr)return -1;
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        return best( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

void solve(int l,int r,int minh){
    if(l>r)return;

    int curr=getmax(1,0,n-1,l,r);
    if(h[curr]<minh)return;

    solve(l,curr-1,minh);
    poss.push_back(curr);
    solve(curr+1,r,minh);
}

long long min_distance(vector<int> x,vector<int> H,vector<int> l,vector<int> r,vector<int> y,int s, int g){
    n=int(x.size()); m=int(l.size());

    for(int i=0;i<n;i++){
        h[i]=H[i];
    }
    build(1,0,n-1);

    mp[{x[s],0}]=1;
    mp[{x[g],0}]=2; 
    z=2;

    for(int i=0;i<m;i++){
        poss.clear();
        solve(l[i],r[i],y[i]);

        for(int f:poss){
            z++; mp[{x[f],y[i]}]=z;
            w[f].push_back(y[i]);
        }
    }

    for(int i=0;i<n;i++){
        if(i==s or i==g)w[i].push_back(0);
        if(!w[i].empty())sort(w[i].begin(),w[i].end());

        for(int f=0;f<int(w[i].size())-1;f++){
            add_edge(mp[{x[i],w[i][f]}],mp[{x[i],w[i][f+1]}],w[i][f+1]-w[i][f]);
        }
    }


    for(int i=0;i<m;i++){
        poss.clear();
        solve(l[i],r[i],y[i]);

        for(int f=0;f<poss.size()-1;f++){
            add_edge(mp[{x[poss[f]],y[i]}],mp[{x[poss[f+1]],y[i]}],x[poss[f+1]]-x[poss[f]]);
        }
    }

    dijkstra();
    if(dist[2]==inf)return -1;
    return dist[2];
}
 
/*
int main(){
 
    cout<<min_distance({0, 3, 5, 7, 10, 12, 14}, {8, 7, 9, 7, 6, 6, 9}, {0, 0, 0, 2, 2, 3, 4}, {1, 2, 6, 3, 6, 4, 6}, {1, 6, 8, 1, 7, 2, 5}, 1, 5)<<"\n";
    //cout<<min_distance({0, 4, 5, 6, 9}, {6, 6, 6, 6, 6},{3, 1, 0},{4, 3, 2},{1, 3, 6},0, 4)<<"\n";

    return 0;
}
*/

Compilation message (stderr)

walk.cpp: In function 'void dijkstra()':
walk.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int f=0;f<poss.size()-1;f++){
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43