제출 #1036489

#제출 시각아이디문제언어결과실행 시간메모리
1036489AbitoSky Walking (IOI19_walk)C++17
0 / 100
2324 ms308352 KiB
#include "walk.h" #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define int long long #define ep insert #define elif else if using namespace std; const int N=1e5+5; int n,m,a[N],b[N],L[N],R[N],c[N],dis[N][15]; vector<pair<int,int>> ad[N],er[N]; vector<int> v[N]; set<int> s[N]; bool vis[N][15]; void dijkstra(int src){ for (int i=1;i<=n;i++) for (int j=0;j<15;j++) dis[i][j]=LLONG_MAX; dis[src][11]=0; priority_queue<vector<int>> pq; pq.push({0,src,11}); while (!pq.empty()){ int x=pq.top()[1],y=pq.top()[2]; pq.pop(); if (vis[x][y]) continue; //cout<<x<<' '<<y<<endl; vis[x][y]=1; int h; if (y==11) h=0; elif (y==12) h=b[x]; else h=c[v[x][y]]; for (int i=0;i<v[x].size();i++){ if (dis[x][i]>dis[x][y]+abs(c[v[x][i]]-h)){ dis[x][i]=dis[x][y]+abs(c[v[x][i]]-h); pq.push({-dis[x][i],x,i}); } } if (dis[x][11]>dis[x][y]+h){ dis[x][11]=dis[x][y]+h; pq.push({-dis[x][11],x,11}); } if (dis[x][12]>dis[x][y]+b[x]-h){ dis[x][12]=dis[x][y]+b[x]-h; pq.push({-dis[x][12],x,12}); } if (y>10) continue; auto it=s[v[x][y]].upper_bound(x); if (it!=s[v[x][y]].end()){ int tox=*it,toy; for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i; if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){ dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]); pq.push({-dis[tox][toy],tox,toy}); } } it=s[v[x][y]].lower_bound(x); if (it!=s[v[x][y]].begin()){ int tox=*--it,toy; for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i; if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){ dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]); pq.push({-dis[tox][toy],tox,toy}); } } } return; } long long 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(); for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i]; for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j]; for (int j=1;j<=m;j++){ ad[L[j]].pb({c[j],j}); er[R[j]].pb({c[j],j}); } set<pair<int,int>> ms; for (int i=1;i<=n;i++){ for (auto u:ad[i]) ms.ep(u); for (auto u:ms){ if (u.F<=b[i]) v[i].pb(u.S),s[u.S].ep(i); else break; } for (auto u:er[i]) ms.erase(u); } dijkstra(S+1); if (dis[g+1][11]==LLONG_MAX) return -1; return dis[g+1][11]; }

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

walk.cpp: In function 'void dijkstra(long long int)':
walk.cpp:31: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]
   31 |         for (int i=0;i<v[x].size();i++){
      |                      ~^~~~~~~~~~~~
walk.cpp:49:27: 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]
   49 |             for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:58:27: 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]
   58 |             for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:59:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^
walk.cpp:50:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^
#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...