oj.uz

Submission #762534

# Submission time Handle Problem Language Result Execution time Memory
762534 2023-06-21T13:10:22 Z alexander707070 Sky Walking (IOI19_walk) C++14
24 / 100
 3337 ms 894316 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 45 ms 94164 KB Output is correct
3 Correct 44 ms 94188 KB Output is correct
4 Correct 43 ms 94212 KB Output is correct
5 Correct 46 ms 94336 KB Output is correct
6 Correct 44 ms 94228 KB Output is correct
7 Correct 44 ms 94240 KB Output is correct
8 Correct 45 ms 94280 KB Output is correct
9 Correct 45 ms 94156 KB Output is correct
10 Correct 45 ms 94364 KB Output is correct
11 Correct 47 ms 94176 KB Output is correct
12 Correct 45 ms 94240 KB Output is correct
13 Correct 44 ms 94260 KB Output is correct
14 Correct 44 ms 94180 KB Output is correct
15 Correct 45 ms 94152 KB Output is correct
16 Correct 47 ms 94276 KB Output is correct
17 Correct 54 ms 94296 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 42 ms 94160 KB Output is correct
3 Correct 1648 ms 191020 KB Output is correct
4 Correct 1443 ms 193856 KB Output is correct
5 Correct 1119 ms 179416 KB Output is correct
6 Correct 933 ms 168112 KB Output is correct
7 Correct 1076 ms 179600 KB Output is correct
8 Correct 2202 ms 217452 KB Output is correct
9 Correct 1192 ms 179772 KB Output is correct
10 Correct 2289 ms 234388 KB Output is correct
11 Correct 763 ms 144456 KB Output is correct
12 Correct 393 ms 123368 KB Output is correct
13 Correct 1831 ms 216756 KB Output is correct
14 Correct 445 ms 122424 KB Output is correct
15 Correct 476 ms 126540 KB Output is correct
16 Correct 461 ms 128844 KB Output is correct
17 Correct 426 ms 127556 KB Output is correct
18 Correct 428 ms 130616 KB Output is correct
19 Correct 55 ms 95788 KB Output is correct
20 Correct 170 ms 110068 KB Output is correct
21 Correct 389 ms 127016 KB Output is correct
22 Correct 382 ms 126412 KB Output is correct
23 Correct 619 ms 135648 KB Output is correct
24 Correct 396 ms 127476 KB Output is correct
25 Correct 419 ms 127232 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 106444 KB Output is correct
2 Runtime error 3337 ms 894316 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 106444 KB Output is correct
2 Runtime error 3337 ms 894316 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 45 ms 94164 KB Output is correct
3 Correct 44 ms 94188 KB Output is correct
4 Correct 43 ms 94212 KB Output is correct
5 Correct 46 ms 94336 KB Output is correct
6 Correct 44 ms 94228 KB Output is correct
7 Correct 44 ms 94240 KB Output is correct
8 Correct 45 ms 94280 KB Output is correct
9 Correct 45 ms 94156 KB Output is correct
10 Correct 45 ms 94364 KB Output is correct
11 Correct 47 ms 94176 KB Output is correct
12 Correct 45 ms 94240 KB Output is correct
13 Correct 44 ms 94260 KB Output is correct
14 Correct 44 ms 94180 KB Output is correct
15 Correct 45 ms 94152 KB Output is correct
16 Correct 47 ms 94276 KB Output is correct
17 Correct 54 ms 94296 KB Output is correct
18 Correct 43 ms 94156 KB Output is correct
19 Correct 42 ms 94160 KB Output is correct
20 Correct 1648 ms 191020 KB Output is correct
21 Correct 1443 ms 193856 KB Output is correct
22 Correct 1119 ms 179416 KB Output is correct
23 Correct 933 ms 168112 KB Output is correct
24 Correct 1076 ms 179600 KB Output is correct
25 Correct 2202 ms 217452 KB Output is correct
26 Correct 1192 ms 179772 KB Output is correct
27 Correct 2289 ms 234388 KB Output is correct
28 Correct 763 ms 144456 KB Output is correct
29 Correct 393 ms 123368 KB Output is correct
30 Correct 1831 ms 216756 KB Output is correct
31 Correct 445 ms 122424 KB Output is correct
32 Correct 476 ms 126540 KB Output is correct
33 Correct 461 ms 128844 KB Output is correct
34 Correct 426 ms 127556 KB Output is correct
35 Correct 428 ms 130616 KB Output is correct
36 Correct 55 ms 95788 KB Output is correct
37 Correct 170 ms 110068 KB Output is correct
38 Correct 389 ms 127016 KB Output is correct
39 Correct 382 ms 126412 KB Output is correct
40 Correct 619 ms 135648 KB Output is correct
41 Correct 396 ms 127476 KB Output is correct
42 Correct 419 ms 127232 KB Output is correct
43 Correct 200 ms 106444 KB Output is correct
44 Runtime error 3337 ms 894316 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -