제출 #901252

#제출 시각아이디문제언어결과실행 시간메모리
901252abcvuitunggioSky Walking (IOI19_walk)C++17
24 / 100
1569 ms441388 KiB
#include "walk.h" #include <bits/stdc++.h> #define int long long using namespace std; const int INF=1e18; priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q; vector <int> a[100001],b[100001],V; vector <pair <int, int>> ke[12000001],ve,nodes; int n,m,d[12000001],dp[200001],ft[200001][2]; set <int> S; void add(int i, int j){ a[i].push_back(j); nodes.push_back({i,j}); } int f(int i, int j){ return lower_bound(nodes.begin(),nodes.end(),make_pair(i,j))-nodes.begin(); } void update(int i, int j, int val){ for (;i<=V.size();i+=i&(-i)) ft[i][j]=min(ft[i][j],val); } int get(int i, int j){ int res=INF; for (;i;i-=i&(-i)) res=min(res,ft[i][j]); return res; } int min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g){ n=x.size(),m=l.size(); int ch=1; for (int i=1;i<n;i++) ch&=(h[i]==h[0]); if (s>g) swap(s,g); if (s==0&&g==n-1&&ch){ for (int i=0;i<m;i++){ ve.push_back({l[i],y[i]}); if (r[i]==g) ve.push_back({r[i],y[i]}); } sort(ve.begin(),ve.end()); for (auto [i,j]:ve) V.push_back(j); sort(V.begin(),V.end()); V.resize(unique(V.begin(),V.end())-V.begin()); for (int i=0;i<=V.size();i++) ft[i][0]=ft[i][1]=INF; for (int i=ve.size()-1;i>=0;i--){ int Y=ve[i].second,j=lower_bound(V.begin(),V.end(),Y)-V.begin()+1; if (ve[i].first==g) dp[i]=Y; else dp[i]=min(get(V.size()-j+1,0)-Y,get(j,1)+Y); update(V.size()-j+1,0,dp[i]+Y); update(j,1,dp[i]-Y); } return dp[0]+ve[0].second+x[g]-x[s]; } for (int i=0;i<n;i++) ve.push_back({-h[i],-i}); for (int i=0;i<m;i++) ve.push_back({-y[i],i+1}); sort(ve.begin(),ve.end()); for (auto [i,j]:ve){ i=-i,j=-j; if (j>=0){ S.insert(j); continue; } j=-j-1; for (auto it=S.lower_bound(l[j]);it!=S.end()&&*it<=r[j];it++){ add(*it,j); b[j].push_back(*it); } } add(s,-1); add(g,-1); sort(nodes.begin(),nodes.end()); nodes.resize(unique(nodes.begin(),nodes.end())-nodes.begin()); for (int i=0;i<n;i++) for (int j=0;j<(int)a[i].size()-1;j++){ int u=f(i,a[i][j]),v=f(i,a[i][j+1]),w=abs((a[i][j]>=0?y[a[i][j]]:0)-(a[i][j+1]>=0?y[a[i][j+1]]:0)); ke[u].push_back({v,w}); ke[v].push_back({u,w}); } for (int i=0;i<m;i++) for (int j=0;j<(int)b[i].size()-1;j++){ int u=f(b[i][j],i),v=f(b[i][j+1],i),w=x[b[i][j+1]]-x[b[i][j]]; ke[u].push_back({v,w}); ke[v].push_back({u,w}); } fill(d,d+nodes.size(),INF); d[f(s,-1)]=0; q.push({0,f(s,-1)}); while (!q.empty()){ auto [du,u]=q.top(); q.pop(); if (du!=d[u]) continue; for (auto [v,w]:ke[u]) if (d[v]>d[u]+w){ d[v]=d[u]+w; q.push({d[v],v}); } } return (d[f(g,-1)]==INF?-1:d[f(g,-1)]); }

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'void update(long long int, long long int, long long int)':
walk.cpp:19:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (;i<=V.size();i+=i&(-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>, int32_t, int32_t)':
walk.cpp:46:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i=0;i<=V.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...