Submission #145288

#TimeUsernameProblemLanguageResultExecution timeMemory
145288Bodo171Sky Walking (IOI19_walk)C++14
10 / 100
67 ms10144 KiB
#include "walk.h" #include <queue> #include <vector> #include <algorithm> #include <climits> #include <iostream> using namespace std; const int nmax=10005; queue<int> q; vector< pair<int,long long > >v[nmax]; vector<int> rel,newrel; int norm[105][105]; int bune[nmax]; long long d[nmax]; int n,nr,i,j; void add(int x,int y,int z) { v[x].push_back({y,z}); v[y].push_back({x,z}); } long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) { n=x.size(); rel.push_back(0); for(i=0;i<y.size();i++) rel.push_back(y[i]); for(i=0;i<h.size();i++) rel.push_back(h[i]); sort(rel.begin(),rel.end()); for(i=0;i<rel.size();i++) if(i==0||rel[i]!=rel[i-1]) newrel.push_back(rel[i]); rel=newrel; int cate=rel.size(); for(i=0;i<n;i++) for(j=0;j<cate;j++) norm[i][j]=++nr; for(i=0;i<n;i++) { for(j=0;j<cate-1;j++) { add(norm[i][j],norm[i][j+1],rel[j+1]-rel[j]); } } for(i=1;i<=nr;i++) d[i]=LLONG_MAX; int m=l.size(); for(i=0;i<m;i++) { int p=0,nr_bune=0; while(y[i]>rel[p]) p++; for(int t=l[i];t<=r[i];t++) if(h[t]>=y[i]) bune[++nr_bune]=t; for(int t=1;t<nr_bune;t++) add(norm[bune[t]][p],norm[bune[t+1]][p],x[bune[t+1]]-x[bune[t]]); } d[norm[s][0]]=0; q.push(norm[s][0]); while(!q.empty()) { int X=q.front(),nod;q.pop(); for(i=0;i<v[X].size();i++) { nod=v[X][i].first; if(d[X]+v[X][i].second<d[nod]) { d[nod]=d[X]+v[X][i].second; q.push(nod); } } } if(d[norm[g][0]]==LLONG_MAX) d[norm[g][0]]=-1; return d[norm[g][0]]; }

Compilation message (stderr)

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:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++)
             ~^~~~~~~~~
walk.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<h.size();i++)
             ~^~~~~~~~~
walk.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<rel.size();i++)
             ~^~~~~~~~~~~
walk.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[X].size();i++)
                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...