oj.uz

Submission #762524

# Submission time Handle Problem Language Result Execution time Memory
762524 2023-06-21T12:58:02 Z alexander707070 Sky Walking (IOI19_walk) C++14
0 / 100
 2392 ms 894740 KB 
#include<bits/stdc++.h>
#define MAXN 2000007
using namespace std;

const long long inf=1e16;

int n,m,z,minv,last,j; 
map< pair<int,int>, int > mp;
vector<int> w[MAXN];
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});
        }
    }
}

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());

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

    for(int i=0;i<m;i++){
        for(int f=l[i];f<=r[i];f++){
            if(h[f]<y[i])continue;
            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<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]);
        }
    }

    j=1;
    for(long long i=0;i<100000000;i++){
        j*=82633; j%=47574;
    }

    for(int i=0;i<m;i++){
        last=-1;
        for(int f=l[i];f<=r[i];f++){
            if(h[f]<y[i])continue;
            if(last!=-1)add_edge(mp[{x[last],y[i]}],mp[{x[f],y[i]}],x[f]-x[last]);
            last=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:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int f=0;f<w[i].size()-1;f++){
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 94228 KB Output is correct
2 Correct 441 ms 94212 KB Output is correct
3 Correct 442 ms 94284 KB Output is correct
4 Runtime error 112 ms 190796 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 94224 KB Output is correct
2 Correct 443 ms 94228 KB Output is correct
3 Correct 1739 ms 190772 KB Output is correct
4 Correct 1546 ms 192540 KB Output is correct
5 Runtime error 415 ms 285264 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 106308 KB Output is correct
2 Runtime error 2392 ms 894740 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 538 ms 106308 KB Output is correct
2 Runtime error 2392 ms 894740 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 442 ms 94228 KB Output is correct
2 Correct 441 ms 94212 KB Output is correct
3 Correct 442 ms 94284 KB Output is correct
4 Runtime error 112 ms 190796 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -